LeetCode 112 Path Sum：二叉樹路徑總和判斷（遞歸 DFS）

問題描述

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

遞歸解法

深度優先搜索，遞歸參數為當前節點和剩餘目標值。到達葉節點時檢查剩餘值是否等於該節點值。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        return dfs(root, sum);
    }
    bool dfs(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right) // 葉節點
            return sum == root->val;
        return dfs(root->left, sum - root->val) || dfs(root->right, sum - root->val);
    }
};

要點

• 空樹返回 false。
• 葉節點判斷條件：`!left && !right`。
• 遞歸將問題分解為左右子樹的子問題，目標值遞減。
• 時間複雜度 O(n)，空間複雜度 O(h)（遞歸棧深度，最壞 O(n)）。

迭代寫法（棧模擬）

bool hasPathSum(TreeNode* root, int sum) {
    if (!root) return false;
    stack<pair<TreeNode*, int>> st;
    st.emplace(root, sum - root->val);
    while (!st.empty()) {
        auto [node, cur] = st.top(); st.pop();
        if (!node->left && !node->right && cur == 0) return true;
        if (node->right) st.emplace(node->right, cur - node->right->val);
        if (node->left) st.emplace(node->left, cur - node->left->val);
    }
    return false;
}

此題是樹形 DP / DFS 入門經典，掌握遞歸與迭代兩種寫法，面試常考。