leetcode link

leetcode tree visualize: https://eniac00.github.io/btv/

Description

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.

---

이진 트리 root가 주어졌을 때, root에서 X 노드로 가는 경로에 X 보다 큰 값이 없을떄 good이라고 한다.

이진 트리에서 good 노드의 개수를 반환하세요.

예시 1:

입력: root = [3,1,4,3,null,1,5]
출력: 4
설명: 파란색으로 표시된 노드들이 good입니다.
root 노드 (3)은 항상 good 노드입니다.
노드 4 -> (3,4)는 root에서 시작하는 경로에서 최대값입니다.
노드 5 -> (3,4,5)는 경로에서 최대값입니다.
노드 3 -> (3,1,3)은 경로에서 최대값입니다.

예시 2:

입력: root = [3,3,null,4,2]
출력: 3
설명: 노드 2 -> (3, 3, 2)는 good하지 않습니다, "3"이 그것보다 높기 때문입니다.

예시 3:
입력: root = [1]
출력: 1
설명: root는 good으로 간주됩니다.

제약 사항:

• 이진 트리의 노드 수는 [1, 10^5] 범위에 있습니다.
• 각 노드의 값은 [-10^4, 10^4] 사이입니다.

Solution

class Solution {
    int good = 0;

    public int goodNodes(TreeNode root) {
        dfs(root, Integer.MIN_VALUE);

        return good;
    }

    void dfs(TreeNode node, int maxValue) {
        if (node == null)
            return;

        if (node.val >= maxValue) {
            maxValue = node.val;
            good++;
        }
        dfs(node.left, maxValue);
        dfs(node.right, maxValue);
    }
}