Count Good Nodes in Binary Tree
題目描述
給定一棵二元樹的根節點 root。節點 X 是 good node，如果從根到 X 的路徑上沒有任何節點的值大於 X。回傳 good node 的數量。
輸入: 3
/ \
1 4
/ / \
3 1 5
輸出: 4
解釋: Good nodes: 3(根), 3(左下), 4, 5
解題思路
從根開始 DFS
呼叫 dfs(root, root.val)，根節點永遠是 good node
到達每個節點
比較 node.val 和 maxSoFar（從根到此的路徑最大值）
判斷 Good Node
若 node.val ≥ maxSoFar，count 加 1；否則不計入
更新最大值
計算 newMax = max(maxSoFar, node.val)，傳給左右子樹的遞迴呼叫
匯總
回傳 count + dfs(left, newMax) + dfs(right, newMax) 累加所有子樹結果
程式碼
C#
public class Solution {
public int GoodNodes(TreeNode root) {
return Dfs(root, root.val);
}
private int Dfs(TreeNode node, int maxSoFar) {
if (node == null) return 0;
int count = node.val >= maxSoFar ? 1 : 0;
int newMax = Math.Max(maxSoFar, node.val);
count += Dfs(node.left, newMax);
count += Dfs(node.right, newMax);
return count;
}
}TypeScript
function goodNodes(root: TreeNode | null): number {
function dfs(node: TreeNode | null, maxSoFar: number): number {
if (!node) return 0;
const count = node.val >= maxSoFar ? 1 : 0;
const newMax = Math.max(maxSoFar, node.val);
return count + dfs(node.left, newMax) + dfs(node.right, newMax);
}
return dfs(root, root!.val);
}Python
def goodNodes(root: TreeNode) -> int:
def dfs(node, max_so_far):
if not node:
return 0
count = 1 if node.val >= max_so_far else 0
new_max = max(max_so_far, node.val)
return count + dfs(node.left, new_max) + dfs(node.right, new_max)
return dfs(root, root.val)複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(h) |
h 是樹高，最壞 O(n)（skewed tree）。Time O(n) 是因為每個節點恰好訪問一次、做一次比較和一次 max 運算。Space O(h) 是遞迴 call stack 深度，平衡樹 O(log n)，偏斜樹 O(n)。
邊界情況
- 只有根節點：根永遠是 good node，回傳 1
- 所有值遞減：如
[5,3,1]，只有根是 good node，其他都比路徑最大值小 - 所有值相同：如
[3,3,3,3]，每個節點都 ≥ 路徑最大值，全部都是 good node
圖解
圖表展示了每個節點的 maxSoFar 值和 good/not good 判定：根 3 是 good（無前驅）、左子 1 不是 good（1 小於 3）、右子 4 是 good（4 ≥ 3）、左下 3 是 good（3 ≥ 3）、5 是 good（5 ≥ 4）。共 4 個 good nodes。
進階觀點
💡面試追問
Q: 為什麼根節點一定是 good node？ A: good node 的定義是「路徑上沒有比自己大的節點」。根到自己的路徑只有自己，不存在更大的值，所以根永遠滿足條件。
Q: 如何用 iterative DFS 解？
A: 用 Stack 存 (node, maxSoFar) tuple。每次 pop 出一個節點，判斷是否 good，然後把左右子節點連同更新後的 maxSoFar push 進 Stack。邏輯和遞迴完全對應。
Q: 時間能比 O(n) 更快嗎？ A: 不能。每個節點都必須被檢查才能判斷是否為 good node，所以下界就是 O(n)。
變體題：LC 1026 Maximum Difference Between Node and Ancestor（路徑上的最大差值）。
理解測驗
🤔 節點值為 1，路徑最大值為 3，這個節點是 good node 嗎？
🤔 DFS 時傳遞 maxSoFar 的目的是什麼？