Description
給定一棵二元樹，每個節點值為 0-9。每條根到葉的路徑代表一個數字（如 1->2->3 代表 123）。回傳所有根到葉數字的總和。
Example:
Input: root = [1,2,3] Output: 25 Explanation: 12 + 13 = 25
Intuition#
DFS 往下傳遞當前累積的數字，到葉節點時加入總和。
- 從根到當前節點的數字 = 父節點數字 * 10 + 當前節點值
- 到達葉節點時，該路徑的數字就確定了
- 累加所有葉節點的路徑數字即為答案
Approaches#
1: DFS 遞迴#
- 概念: 遞迴傳遞當前累積的數字，到葉節點時回傳
- 時間複雜度:
O(n) - 空間複雜度:
O(h)，h 為樹高
class Solution {
fun sumNumbers(root: TreeNode?): Int {
return dfs(root, 0)
}
private fun dfs(node: TreeNode?, currentNum: Int): Int {
if (node == null) return 0
val num = currentNum * 10 + node.`val`
if (node.left == null && node.right == null) return num
return dfs(node.left, num) + dfs(node.right, num)
}
}⭐ 2: BFS 迭代#
- 概念: 用佇列做 BFS，每個節點存當前累積的數字，到葉節點時加入總和
- 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun sumNumbers(root: TreeNode?): Int {
if (root == null) return 0
var sum = 0
val queue: Queue<Pair<TreeNode, Int>> = LinkedList()
queue.offer(root to root.`val`)
while (queue.isNotEmpty()) {
val (node, num) = queue.poll()
if (node.left == null && node.right == null) {
sum += num
continue
}
node.left?.let { queue.offer(it to num * 10 + it.`val`) }
node.right?.let { queue.offer(it to num * 10 + it.`val`) }
}
return sum
}
}🔑 Takeaways#
- Pattern: 根到葉路徑問題，DFS 向下傳遞累積狀態是最自然的做法
- 關鍵技巧: 數字累積公式
current * 10 + node.val避免了字串拼接的開銷