Path Sum II

113. 路径总和II

分析

当前节点 root->val 加入 path
从 target 中减去当前节点值
如果当前节点是叶子节点，且 target == 0，说明当前路径满足条件，将 path 加入 res
否则递归左子树和右子树
最后进行回溯，将当前节点从 path 中弹出

时间复杂度

时间复杂度 O(n^2)，最坏情况下每个节点都可能被访问，且每条路径都可能需要复制一份保存到结果中

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    std::vector<std::vector<int>> res;
    std::vector<int> path;

    void dfs(TreeNode* root, int target)
    {
        path.push_back(root->val);     // 添加当前节点到路径
        target -= root->val;           // 更新剩余目标值

        if (!root->left && !root->right)  // 到达叶子节点
        {
            if (target == 0)
                res.push_back(path);      // 满足条件，加入结果
        }
        else
        {
            if (root->left) dfs(root->left, target);   // 递归左子树
            if (root->right) dfs(root->right, target); // 递归右子树
        }

        path.pop_back();   // 回溯，移除当前节点
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum)
    {
        if (root)
            dfs(root, targetSum);  // 从根节点开始DFS
        return res;
    }
};