Leetcode113. 路径总和 II

2021年4月26日 662点热度 2人点赞 1条评论

题目描述

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

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

示例 1:

img

输入: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

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

示例 3:

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

提示:

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

解题思路

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

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

数的DFS遍历过程如下:

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

  • 接着,更新tempPathpathSum的值,以便进行后边的递归调用和条件判断;

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

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

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

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

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

示例代码如下所示。

示例代码

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;
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

  • 乐乐

    早八人来打卡

    2021年4月27日
  • 您需要 登录 之后才可以评论