1448. Count Good Nodes In Binary Tree

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.

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        ans = 0
 
        def recurse(node, maxsofar):
            nonlocal ans
            
            if node:
                if node.val >= maxsofar:
                    ans += 1
                recurse(node.left, max(maxsofar, node.val))
                recurse(node.right, max(maxsofar, node.val))
 
        recurse(root, float("-inf"))
        return ans

• keep track of the maximum node value we’ve seen along the recursion path.
• a node is good if it is $\ge$ that maximum value.

table without id file.inlinks as Backlinks
where file.name = this.file.name

Related.

References.

Categories:: recursion, tree, binary-tree