題目描述:給定一棵只含數字 0–9 的二元樹,從根到每個葉節點的路徑代表一個數字(例如路徑 1 → 2 → 3 代表數字 123)。求所有根到葉路徑所代表的數字之總和。
解題思路:使用深度優先搜尋(DFS),在遞迴向下走的過程中,維護一個「目前累積的數字」cur。每到一個節點,就執行 cur = cur * 10 + node->val,這樣便能在走到葉節點時,得到該路徑對應的完整數字。當節點為葉節點(左右子節點皆為 null)時,直接回傳 cur 作為這條路徑的貢獻值。對非葉節點,則分別遞迴左右子樹並加總回傳。整個過程只需單次 DFS,不需額外空間儲存路徑。
時間複雜度:O(n) — 每個節點恰好被訪問一次,其中 n 為樹的節點總數。
空間複雜度:O(h) — 遞迴呼叫堆疊的深度等於樹高 h。最差情況(退化成鏈狀樹)為 O(n),平衡樹為 O(log n)。
1. Define dfs(node, cur): a. If node is null: return 0 b. cur = cur * 10 + node.val c. If node is a leaf (no left and no right child): return cur d. Return dfs(node.left, cur) + dfs(node.right, cur) 2. Call dfs(root, 0) and return the result
方法一:迭代 DFS(使用明確 Stack)
用 stack 儲存 (node, cur) 配對,模擬遞迴過程。彈出節點時更新 cur = cur * 10 + node->val;若為葉節點則累加到總和;否則將子節點與對應的 cur 值推入 stack。時間複雜度 O(n),空間複雜度 O(h)。
方法二:BFS 層序遍歷
用 queue 儲存 (node, cur) 配對進行層序遍歷。每個節點出 queue 時計算當前路徑數值,到達葉節點時加入總和。實作邏輯與迭代 DFS 相似,但遍歷順序不同。時間複雜度 O(n),空間複雜度 O(w)(w 為樹的最大寬度)。
方法三:路徑字串轉數字
在 DFS 中維護一個字串,抵達葉節點時用 stoi 轉換成整數後加總。邏輯上等價,但字串操作有額外開銷,且數字過大時需改用長整數,不如直接乘以 10 累加來得簡潔。