題目說明

112. Path Sum
     給定一個二元樹的根節點 root 和一個整數目標值 targetSum，請判斷該樹中是否存在一條從根節點到葉節點的路徑，使得沿途節點的值相加等於 targetSum。
     也就是說：是否存在某條「根 → 葉」路徑，使得所有節點值的總和剛好等於目標值。

範例

Input:

root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

Output:

true

解釋：
存在一條路徑：
5 → 4 → 11 → 2，
其總和為 22。

Python 解法

解法 1：遞迴 DFS

class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def hasPathSum(root: TreeNode, targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return targetSum == root.val
return (hasPathSum(root.left, targetSum - root.val) or
hasPathSum(root.right, targetSum - root.val))

解法 2：BFS（Queue）

from collections import deque
def hasPathSum(root: TreeNode, targetSum: int) -> bool:
if not root:
return False
queue = deque([(root, root.val)])
while queue:
node, curr_sum = queue.popleft()
if not node.left and not node.right and curr_sum == targetSum:
return True
if node.left:
queue.append((node.left, curr_sum + node.left.val))
if node.right:
queue.append((node.right, curr_sum + node.right.val))
return False

Java 解法

解法 1：遞迴 DFS

public class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) {
return targetSum == root.val;
}
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
}

解法 2：BFS（Queue）

import java.util.*;
public class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
Queue nodeQueue = new LinkedList<>();
Queue sumQueue = new LinkedList<>();
nodeQueue.add(root);
sumQueue.add(root.val);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.poll();
int currSum = sumQueue.poll();
if (node.left == null && node.right == null && currSum == targetSum) {
return true;
}
if (node.left != null) {
nodeQueue.add(node.left);
sumQueue.add(currSum + node.left.val);
}
if (node.right != null) {
nodeQueue.add(node.right);
sumQueue.add(currSum + node.right.val);
}
}
return false;
}
}

複雜度分析

• 時間複雜度：O(n)，每個節點都會被拜訪一次。
• 空間複雜度：
  • DFS：O(h)，h 為樹的高度。
  • BFS：O(w)，w 為樹的最大寬度。