學習路線/樹 — 深度優先搜尋 (DFS)

1448. 統計二元樹中好節點的數目

Medium

Count Good Nodes in Binary Tree

TreeDepth-First SearchBinary Tree

題目描述

給定一棵二元樹，若從根節點到節點 X 的路徑上，沒有任何節點的值大於 X.val，則 X 為「好節點」。請回傳樹中好節點的總數目。

LeetCode 1448原題連結 →

解法思路

  1. 使用 DFS 由上往下遍歷，攜帶參數 max_val 記錄路徑上曾出現過的最大值
  2. 每到達一個節點，若 node.val >= max_val，該節點為好節點（is_good = 1）
  3. 更新 new_max = max(max_val, node.val) 後繼續遞迴兩側子樹
  4. 最終回傳 is_good + dfs(left, new_max) + dfs(right, new_max)

複雜度分析

  • 時間複雜度：O(n)
  • 空間複雜度：O(h)，h 為樹的高度
Good 節點數
0
313415
演算法準備開始。以 max_val=-∞ 為初始值呼叫 dfs(root, -∞)。每往下一層，把「到目前為止路徑上見過的最大值」作為參數帶下去。
1 / 21