[LeetCode] Count Good Nodes in Binary Tree

https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75

Given a binary tree root, a node X in the tree is named good 

if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

 

Example 1:

Input: root = [3,1,4,3,null,1,5]

Output: 4

Explanation: Nodes in blue are good.

Root Node (3) is always a good node.

Node 4 -> (3,4) is the maximum value in the path starting from the root.

Node 5 -> (3,4,5) is the maximum value in the path

Node 3 -> (3,1,3) is the maximum value in the path.

 

Example 2:

Input: root = [3,3,null,4,2]

Output: 3

Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]

Output: 1

Explanation: Root is considered as good.

 

Constraints:
The number of nodes in the binary tree is in the range [1, 10^5].
Each node's value is between [-10^4, 10^4].

---

또... 리프 트리가 주어지고, 깊이 우선 탐색을 진행하는데...

경로상에 있는 모든 노드들의 값이 현재 위치의 노드 값보다 작으면, 현재 노드는 good node라고 간주한다.

주어진 리프 트리에서 good node가 몇 개인지 세는 문제.

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var goodNodes = function(root) {
    if(!root.left && !root.right){
        return 1;
    }
    const getGoodNodesCount = (root)=>{
        let count = 1;
        let initVal = root.val;
        let max = root.val;
        let prev = 0;
        const check = (root) => {
            if(root.left){
                prev = max;
                max = Math.max(root.left.val, max);
                console.log("left//", "initVal:", initVal, "max:", max, "left:", root.left.val);
                if(root.left.val >= max){
                    count++;
                    console.log("count plus:", count);
                }
                check(root.left);
            }
            if(root.right){
                prev = max;
                max = Math.max(root.right.val, max);
                console.log("right//", "initVal:", initVal, "max:", max, "right:", root.right.val);
                if(root.right.val >= max){
                    count++;
                    console.log("count plus:", count);
                }
                check(root.right);
            }
            if(!root.left && !root.right){
                console.log("한쪽 끝에 다다름")
                max = Math.max(initVal, prev); // 한 쪽 끝에 다다르면 맨 위 노드와 직전 최대값 중 큰 것으로 교체
            }
        }
        check(root);
        return count;
    }
    return getGoodNodesCount(root);
};

 

테스트케이스에 끼워맞추면서 수정하다보니 코드가 엄청 지저분하고..

굳이 관리할 필요 없는 변수도 많이 만들어서 오히려 헷갈린다ㅋㅋ 결국 모든 테스트케이스를 통과하지도 못했다.

 

머리가 빠개질 것 같아서 결국 여기저기 참고해서 만들어낸 코드는 이렇다.

 

var goodNodes = function(root) {
    if(!root.left && !root.right){
        return 1;
    }
    let count = 0;
    const dfs = (node, max) => {
        if(!node){
            return;
        }
        if(node.val >= max){
            count++;
            max = node.val;
        }
        dfs(node.left, max);
        dfs(node.right, max);
    }
    
    dfs(root, root.val);

    return count;
};

 

내가 작성했던 코드의 문제점이 한 쪽 분기의 끝에 다다랐을 때,

이전 분기까지의 max를 제대로 가져오지 못한다는 거였는데...

이렇게 하면 갱신 전의 max를 인자로 같이 넣어줌으로써 분기점마다 max가 균일하게 관리된다.

 

 

당연한 말이지만 리프트리 문제들의 답이 되는 코드는 결국 다 생긴 게 비슷비슷한데 한끗차이로 다른 문제의 답이 된다는게 웃기다..