LeetCode 1448. Count Good Nodes in Binary Tree

Intuition

Use global counter and dfs to count number of good nodes.

1. Initialize self.count to count good nodes
2. if current node's val is greater than max_val of the previous path increment self.count
3. traverse down left and right child and update the max_val parameter

Optimal Solution

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        self.count = 0
        def countGood(node, max_val):
            if not node:
                return
            if node.val >= val:
                self.count += 1
            countGood(node.left, max(val, node.val))
            countGood(node.right, max(val, node.val))

        countGood(root, root.val)
        return self.count

Time Complexity

Time Complexity O(N)

Space Complexity O(H)