題目描述:給定一棵二元樹的根節點 root 和整數 targetSum,判斷是否存在一條從根節點到葉節點的路徑,使得路徑上所有節點的值之和等於 targetSum。葉節點定義為沒有任何子節點的節點。
解題思路:使用深度優先搜尋(DFS)遞迴實作。每到一個節點,就將 targetSum 減去當前節點的值,代表「剩餘需要湊到的目標」。到達葉節點時,若剩餘目標恰好為 0,表示找到了合法路徑,回傳 true。否則遞迴地對左子樹和右子樹分別搜尋,只要任一子樹回傳 true 即可。空節點直接回傳 false(空樹不含任何路徑)。此遞迴自然地模擬了「路徑從根到葉」的條件,無需額外記錄路徑。
時間複雜度:O(n) — 最差情況下(答案不存在)需遍歷所有 n 個節點;最佳情況下找到答案可提前返回。
空間複雜度:O(h) — h 為樹的高度,對應遞迴呼叫堆疊深度。平衡樹 O(log n),鏈狀樹(最差)O(n)。
1. If root is null, return false. 2. Compute remaining = targetSum - root.val. 3. If root is a leaf (no left and no right child): - Return (remaining == 0). 4. Return hasPathSum(root.left, remaining) OR hasPathSum(root.right, remaining).
方法一:DFS 遞迴(最優解) — 如本題解,時間 O(n)、空間 O(h)(遞迴堆疊)。程式碼簡潔,直觀表達問題結構。
方法二:BFS 迭代(層序遍歷) — 使用佇列,同時儲存每個節點對應的「到達該節點時累積的路徑和」。到達葉節點時判斷是否等於 targetSum。時間 O(n)、空間 O(n)(佇列最大存一整層節點)。適合需要避免遞迴堆疊溢位的場景。
方法三:DFS 迭代(模擬堆疊) — 用顯式 Stack 模擬 DFS,同樣儲存 (節點, 剩餘目標) 配對,時間 O(n)、空間 O(h),行為與遞迴相同但不依賴系統呼叫堆疊。