LeetCode 112. Path Sum：二叉樹路徑總和遞歸判定

問題描述

給定二叉樹根節點 root 和目標和 sum，判斷是否存在從根到葉的路徑，節點值之和等於 sum。葉節點無子節點。
例：樹 [5,4,8,11,null,13,4,7,2,null,null,null,1]，sum=22，路徑 5→4→11→2 和為 22，返回 true。

遞歸解法

將問題轉化為子問題：當前節點值為 val，剩餘目標和為 sum-val，遞歸檢查左右子樹：

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    int remaining = sum - root.val;
    if (root.left == null && root.right == null)  // 葉節點
        return remaining == 0;
    return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

關鍵點

• 基線條件：空節點返回 false；葉節點檢查剩餘和是否為 0
• 遞歸傳遞剩餘目標和，避免額外累加變量
• 短路求值：左子樹找到即返回，不必搜索右子樹

迭代替代方案（DFS/BFS）

// DFS 顯式棧
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    Deque> stack = new ArrayDeque<>();
    stack.push(new Pair<>(root, sum - root.val));
    while (!stack.isEmpty()) {
        Pair p = stack.pop();
        TreeNode node = p.getKey(); int rem = p.getValue();
        if (node.left == null && node.right == null && rem == 0) return true;
        if (node.right != null) stack.push(new Pair<>(node.right, rem - node.right.val));
        if (node.left != null) stack.push(new Pair<>(node.left, rem - node.left.val));
    }
    return false;
}

複雜度

• 時間：O(n)，最壞訪問所有節點
• 空間：遞歸 O(h)，迭代 O(h)，最壞 O(n)