LeetCode 112：路徑總和（遞歸 DFS 判斷根到葉路徑）

題目描述

給定二叉樹根節點和目標和 sum，判斷是否存在從根到葉的路徑，使路徑上節點值之和等於 sum。

遞歸解法

若根為空返回 false。若為葉子節點，判斷值是否等於剩餘 sum。否則遞歸檢查左右子樹，目標和減去當前節點值。

代碼實現 (C++)

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);
    }
};

另一種累加寫法

傳遞當前累加和，到葉子時比較是否等於目標 sum。

bool dfs(TreeNode* root, int cur, int target) {
    if (!root) return false;
    cur += root->val;
    if (!root->left && !root->right) return cur == target;
    return dfs(root->left, cur, target) || dfs(root->right, cur, target);
}
bool hasPathSum(TreeNode* root, int sum) {
    return dfs(root, 0, sum);
}

複雜度

• 時間：O(n)
• 空間：O(h)