1448.count-good-nodes-in-binary-tree.md

1448. Count Good Nodes in Binary Tree

DFS

We just trace the current maximum value from the root to the current node.

fun goodNodes(root: TreeNode?): Int {
    return dfs(root, root.`val`)
}

private fun dfs(root: TreeNode?, max: Int): Int {
    if (root == null) return 0
    var count = if (root.`val` >= max) 1 else 0

    val nextMax = maxOf(max, root.`val`)
    count += dfs(root.left, nextMax)
    count += dfs(root.right, nextMax)
    return count
}

• Time Complexity: O(n) where n is the number of nodes in the tree.
• Space Complexity: O(h) where h is the height of the tree.