LeetCode 113: Path Sum II - 二叉樹路徑總和回溯

問題描述

給定二叉樹根節點和目標和，找出所有從根到葉子節點路徑節點值之和等於目標和的路徑。

回溯算法

遞歸函數 dfs(node, remaining, path, result)：
- 將節點值加入 path。
- 若為葉子且 node.val == remaining，將 path 加入 result。
- 否則遞歸左右子節點，remaining - node.val。
- 回溯：彈出 path 末尾。

關鍵細節

• 傳遞 path 為值拷貝或引用+回溯，注意恢復現場。
• 空樹直接返回空列表。
• 葉子判斷：!node.left && !node.right。

C++ 代碼

void dfs(TreeNode* root, int sum, vector& path, vector>& res) {
    if (!root) return;
    path.push_back(root->val);
    if (!root->left && !root->right && root->val == sum) {
        res.push_back(path);
    } else {
        dfs(root->left, sum - root->val, path, res);
        dfs(root->right, sum - root->val, path, res);
    }
    path.pop_back();
}