1448. Count Good Nodes in Binary Tree

Question: Count Good Nodes in Binary Tree

Solution

思考：

children 只要大於等於所有的 ancestor，就是 Good Node。

因此記下該 path 的最大值 max_val 就好，用 max_val 去與該 node.val 做比較，如果 node.val ≥ max_val 則 node 為 Good Node。

1. Top to Bottom → DFS
2. 拆分問題成子問題：Good Nodes 的總數 = 自己本身是否為 Good Node + left_sub_tree Good Nodes + right_sub_tree Good Nodes

解法：

1. DFS 需要 recursive function，這邊需要把 max_val 傳遞給後面的 node 去做比較，由於原本的 function goodNodes(root) 只能傳遞一個參數，所以需要再寫一個可以傳遞兩個參數的 function: dfs(node, max_val)
2. recursive function 的兩個原則：
   1. 終止條件:
      1. node 為 None 時，代表 Good Node 為 0: if node == None: return 0
   2. 判斷條件與呼叫自己
      1. 如果 node.val 大於 max_val，表示為 Good Node，此時 max_val 也會變成 node.val: if node.val ≥ max_val: max_val = node.val
      2. 如上述所說 Good Node 的總數 = 自己本身是否為 Good Node + left_sub_tree Good Nodes + right_sub_tree Good Nodes 如果 node.val 大於 max_val: return 1 + dfs(node.left, max_val) + dfs(node.right, max_val) 若否: return 0 + dfs(node.left, max_val) + dfs(node.right, max_val)
3. return dfs(root, root.val)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, max_val):
            if node == None:
                return 0
            if node.val >= max_val:
                max_val = node.val
                return 1 + dfs(node.left, max_val) + dfs(node.right, max_val)
            return dfs(node.left, max_val) + dfs(node.right, max_val) 
        return dfs(root, root.val)

Video Solution