1448. Count Good Nodes in Binary Tree

Count Good Nodes in Binary Tree - LeetCode

주어진 이진 트리에서 좋은 노드를 찾고, 좋은 노드의 개수를 반환하세요.
이 문제에서 좋은 노드는 다음과 같이 정의됩니다: 루트 노드부터 해당 노드까지의 경로 상에서 해당 노드의 값보다 큰 값을 가진 노드가 없는 노드입니다.

 

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.

 

문제 요약: 

루트 노드부터 시작하여 각 노드를 검사하고, 해당 노드의 경로 상에서 더 큰 값을 가진 노드가 없으면 해당 노드는 좋은 노드로 간주합니다. 좋은 노드의 개수를 반환하세요.

 

풀이과정: 

이 문제는 깊이 우선 탐색(DFS)을 사용하여 해결할 수 있습니다. 루트 노드에서 시작하여 각 노드를 검사하고 경로 상에서 더 큰 값을 가진 노드가 없으면 해당 노드는 좋은 노드로 간주합니다.

1. 좋은 노드의 개수를 저장할 변수 goodNodeCount를 초기화합니다.
2. DFS를 사용하여 트리를 탐색합니다. 이때, 현재 노드의 값 nodeValue와 현재 경로 상에서 가장 큰 값 maxValue를 추적합니다.
3. 각 노드에서 다음과 같은 작업을 수행합니다:
   - 현재 노드의 값 nodeValue와 현재 경로 상의 최대값 maxValue를 비교합니다.
     만약 nodeValue가 maxValue보다 크다면, 현재 노드는 좋은 노드입니다. goodNodeCount를 1 증가시킵니다.
   그렇지 않다면, 현재 노드는 좋은 노드가 아닙니다.
     DFS를 왼쪽 서브트리와 오른쪽 서브트리로 재귀적으로 적용합니다.
4. 마지막으로 goodNodeCount를 반환합니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int goodNodes(TreeNode root) {
        return getGoodNodeCnt(root, Integer.MIN_VALUE);
    }
    
    private int getGoodNodeCnt(TreeNode node, int maxValue){
        int goodNodeCnt = 0;
        if(node == null) return 0;

        if(node.val >= maxValue){
            goodNodeCnt++;
            maxValue = node.val;
        }

        goodNodeCnt += getGoodNodeCnt(node.left, maxValue);
        goodNodeCnt += getGoodNodeCnt(node.right, maxValue);

        return goodNodeCnt;
    }
}