LeetCode 113：路徑總和 II——二叉樹 DFS 回溯

題目描述

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

示例

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
sum = 22
輸出：[[5,4,11,2], [5,8,4,5]]

遞歸回溯算法

1. 維護當前路徑 path 和結果集 paths
2. DFS 遍歷：進入節點將值加入 path
3. 若為葉子且剩餘和等于節點值 → 加入結果
4. 遞歸左右子樹，剩餘和減去當前節點值
5. 回溯：退出節點時從 path 彈出值

C++ 實現

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> paths;
        vector<int> path;
        dfs(root, sum, paths, path);
        return paths;
    }
private:
    void dfs(TreeNode* node, int sum,
             vector<vector<int>>& paths,
             vector<int>& path) {
        if (!node) return;
        path.push_back(node->val);
        if (!node->left && !node->right && node->val == sum)
            paths.push_back(path);
        dfs(node->left,  sum - node->val, paths, path);
        dfs(node->right, sum - node->val, paths, path);
        path.pop_back();
    }
};

複雜度

• 時間：O(n) —— 每個節點訪問一次
• 空間：O(h) —— 遞歸棧深度 + 路徑存儲，h 為樹高

效能圖示