Leetcode113. 路径总和 II

题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

img

1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

img

1
2
输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

1
2
输入：root = [1,2], targetSum = 0
输出：[]

提示：

  • 树中节点总数在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

解题思路

这道题我们可以直接套用树的DFS遍历模板来求解，但是需要注意实现时的小细节。

在求解的过程中，用全局的二维vector数组path来存储要求解的路径，在DFS函数内部用非引用的一维vector数组tempPath来保存当前的路径，用非引用的变量pathSum来表示当前的路径和。对tempPath和pathSum用非引用的目的，就是利用递归调用和返回的特性自动更新它们的值，如果使用引用的话，需要自己手动进行回溯，比较繁琐。

数的DFS遍历过程如下：

  • 首先设置递归出口，结点为空的时候直接返回；

  • 接着，更新tempPath和pathSum的值，以便进行后边的递归调用和条件判断；

  • 然后进行path数组的更新。当遍历到叶子结点的时候，如果当前路径的路径和与targetSum一致，那么就把当前路径加入path数组；

    在叶子结点处更新path数组而不在结点为空时更新，目的是避免路径重复，因为每一个叶子结点的左右子树都为空。此外，在结点为空时更新path数组还可能引发一些bad case。

  • 然后递归当前结点的左子树和右子树。

时间复杂度：O(N2)O(N^2)，其中$ N$ 是树的节点数。

空间复杂度：O(N)O(N)，其中$ N$ 是树的节点数。

示例代码如下所示。

示例代码

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
33
34
35
36
37
38
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

vector<vector<int>>path;

void dfs(TreeNode* root,int targetSum,vector<int>tempPath,int pathSum)
{
    if(root==nullptr)
    {
        return;
    }
    pathSum+=root->val;
    tempPath.push_back(root->val);
    if(!root->left&&!root->right)
    {
        if(pathSum==targetSum)
        {
            path.push_back(tempPath);
        }
    }
    dfs(root->left,targetSum,tempPath,pathSum);
    dfs(root->right,targetSum,tempPath,pathSum);

}

vector<vector<int>> pathSum(TreeNode* root, int targetSum)
{
    if(!root) return {};
    vector<int>tempPath;
    dfs(root,targetSum,tempPath,0);
    return path;
}