給定一棵二元樹和一個目標值
targetSum，判斷是否存在一條從根到葉子節點的路徑，使得路徑上所有節點值的總和等於targetSum。
Example:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true (路徑 5 -> 4 -> 11 -> 2 = 22)
Intuition
TIP
從根往下走，每經過一個節點就將目標值減去該節點值，到達葉子時檢查是否剛好為零。
- 遞迴傳遞「剩餘目標值」，每層減去當前節點值
- 注意必須走到葉子節點（左右子節點都為 null）才能判斷
Approaches
⭐ 1. Recursive DFS — O(n) / O(h)
- Idea: 遞迴地將 targetSum 減去當前節點值，到葉子節點時檢查是否為 0
- Time:
O(n)，最差情況需要遍歷所有節點 - Space:
O(h)，遞迴堆疊深度
class Solution {
fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
if (root == null) return false
val remaining = targetSum - root.`val`
if (root.left == null && root.right == null) {
return remaining == 0
}
return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining)
}
}2. Iterative DFS with Stack — O(n) / O(h)
- Idea: 用 Stack 存放節點與剩餘目標值的配對，模擬遞迴過程
- Time:
O(n) - Space:
O(h)
class Solution {
fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
if (root == null) return false
val stack = ArrayDeque<Pair<TreeNode, Int>>()
stack.addLast(root to targetSum)
while (stack.isNotEmpty()) {
val (node, remaining) = stack.removeLast()
val newRemaining = remaining - node.`val`
if (node.left == null && node.right == null && newRemaining == 0) {
return true
}
node.left?.let { stack.addLast(it to newRemaining) }
node.right?.let { stack.addLast(it to newRemaining) }
}
return false
}
}🔑 Takeaways
- Pattern: 路徑和問題 — 遞迴傳遞剩餘值，到葉子節點時做判斷
- Key trick: 「葉子節點」的判斷是左右子節點都為 null，不要忘記這個條件