題目描述:給定一棵二元樹,若從根節點到節點 X 的路徑上,沒有任何節點的值大於 X 的值,則稱 X 為「好節點(Good Node)」。回傳整棵樹中好節點的數量。
解題思路:使用 DFS 遍歷,同時傳遞一個參數 maxSoFar 表示從根到當前節點的路徑上所出現過的最大值。到達每個節點時,若 node->val >= maxSoFar,則該節點為好節點,計數加一,並更新 maxSoFar = max(maxSoFar, node->val) 傳給子節點。由於每個節點只與自身路徑上的最大值比較,無需回溯,因此可直接用前序 DFS(Pre-order DFS)實作。根節點本身必定是好節點(路徑上沒有比它更大的祖先)。
時間複雜度:O(n) — 每個節點恰好被訪問一次。
空間複雜度:O(h) — 遞迴堆疊深度等於樹高 h;最壞情況為 O(n),平衡樹為 O(log n)。
1. Initialize count = 0
2. Define dfs(node, maxSoFar):
a. If node is null, return
b. If node.val >= maxSoFar:
i. count++
ii. maxSoFar = node.val
c. dfs(node.left, maxSoFar)
d. dfs(node.right, maxSoFar)
3. Call dfs(root, -infinity)
4. Return countBFS 層序遍歷 O(n):將 (節點, 路徑最大值) 配對存入佇列,逐層展開。與 DFS 邏輯相同,只是用佇列取代遞迴堆疊。對極深樹可避免遞迴堆疊溢出,但佇列空間最壞為 O(n),通常比 DFS 佔用更多記憶體。
無全域變數的純函式寫法 O(n):將 count 作為回傳值從子呼叫累加,而非使用成員變數。程式碼風格更函式化,無副作用,但邏輯複雜度相同,純屬風格差異。