Count Good Nodes

Medium

Python

def good_nodes(root):
    def dfs(node,max_so_far):
        if not node: return 0
        good=1 if node.val>=max_so_far else 0
        new_max=max(max_so_far,node.val)
        return good+dfs(node.left,new_max)+dfs(node.right,new_max)
    return dfs(root,root.val)

Java

public int goodNodes(TreeNode root){
    return dfs(root,root.val);
}
int dfs(TreeNode node,int maxSoFar){
    if(node==null) return 0;
    int good=node.val>=maxSoFar?1:0;
    int newMax=Math.max(maxSoFar,node.val);
    return good+dfs(node.left,newMax)+dfs(node.right,newMax);
}

Key Insight

Python nested function captures nothing. Java uses helper with parameters.

Python → Java Differences

Nested function vs helper
Python ternary vs Java ternary
DFS with max tracking identical

Python

def good_nodes(root):
    def dfs(node,max_so_far):
        if not node: return 0
        good=1 if node.val>=max_so_far else 0
        new_max=max(max_so_far,node.val)
        return good+dfs(node.left,new_max)+dfs(node.right,new_max)
    return dfs(root,root.val)

Java

public int goodNodes(TreeNode root){
    return dfs(root,root.val);
}
int dfs(TreeNode node,int maxSoFar){
    if(node==null) return 0;
    int good=node.val>=maxSoFar?1:0;
    int newMax=Math.max(maxSoFar,node.val);
    return good+dfs(node.left,newMax)+dfs(node.right,newMax);
}

Algorithm Steps

1. DFS tracking path max
2. Count nodes >= max so far

← Previous All Trees