LeetCode Path Sum：二叉樹路徑總和問題深度解析

問題描述

給定一棵二叉樹和一個目標值 sum，判斷樹中是否存在從根節點到葉節點的路徑，使得路徑上所有節點值的總和等於給定的目標值。

例如：給定如下二叉樹，sum = 22

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

返回 true，因為存在路徑 5→4→11→2，其節點值之和為 22。

核心思路：遞歸深度優先搜索

這是一棵典型的樹結構問題，遞歸是最自然的解法。我們可以將問題轉化為：從根節點出發，每走一步就將目標值減去當前節點的值。當到達葉節點時，檢查剩餘目標值是否等於該葉節點的值。

遞歸終止條件

• 空節點：返回 false，空樹不存在路徑。
• 葉節點：若 node.val == sum 則返回 true，否則返回 false。

遞歸邏輯

對於非葉節點，問題分解為左右子樹的子問題：
hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)

代碼實現 (C++)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        // 到達葉節點，判斷是否滿足條件
        if (!root->left && !root->right) {
            return root->val == sum;
        }
        // 遞歸檢查左右子樹
        return hasPathSum(root->left, sum - root->val) 
            || hasPathSum(root->right, sum - root->val);
    }
};

複雜度分析

• 時間複雜度：O(N)，其中 N 為樹的節點數。最壞情況下需要遍歷所有節點。
• 空間複雜度：O(H)，H 為樹的高度。遞歸調用棧的深度取決於樹的高度。最壞情況（鏈狀樹）為 O(N)，平衡樹為 O(log N)。

進階思考：迭代法

除遞歸外，也可使用棧或隊列實現迭代版 DFS/BFS，手動維護節點及其對應的「剩餘目標值」，邏輯同遞歸本質一致，可避免深度遞歸導致的棧溢出風險。