1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private int ans = 0;

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

    private void dfs(TreeNode node, int currMax) {
        if (node == null) {
            return;
        }
        if (node.val >= currMax) {
            ans += 1;
        }
        dfs(node.left, Math.max(node.val, currMax));
        dfs(node.right, Math.max(node.val, currMax));
    }
}

没什么好说的就是记录一个max即可. 这个就是回溯模板做. 我们不需要下面的node来提供信息给我们来确定当前的答案, 而是边走边统计. 也就是traverse.

时间复杂度: O(n)
空间复杂度: O(n)