题解 | #二叉树中和为某一值的路径(三)#

JZ84 二叉树中和为某一值的路径(三)

题目描述

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。

1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点

2.总节点数目为n

3.保证最后返回的路径个数在整形范围内(即路径个数小于2^31- 1)

方法一：暴力算法

解题思路

对于本题目的求解，可以使用两次深度优先进行解决，第一次深度优先遍历每个结点，将每个节点作为一次根节点，第二次深度优先遍历以每个节点为根的子树，并查找该子树是否有路径和等于给定值的情况。

解题代码

class Solution {
public:
    int res = 0;
    void dfs(TreeNode* root, int sum){ //dfs查询以某结点为根的路径数
        if(root == NULL)
            return;
        if(sum == root->val) //符合目标值
            res++;
        dfs(root->left, sum - root->val); //进入子节点继续找
        dfs(root->right, sum - root->val);
    }
    int FindPath(TreeNode* root, int sum) { //dfs 以每个结点作为根查询路径
        if(root == NULL) //为空则返回
            return res;
        dfs(root, sum); //查询以某结点为根的路径数
        FindPath(root->left, sum); //以其子结点为新根
        FindPath(root->right, sum);
        return res;
    }
};

复杂度分析

时间复杂度：n为二叉树节点，两层dfs，因此时间复杂度为$O(N^2)O(N^2)$。

空间复杂度：每层深度优先的栈深度为n，因此空间复杂度为$O(N)O(N)$

方法二：优化算法

解题思路

基于方法一，我们在进入以某个节点为根的子树的时候，使用哈希表进行记录，当遍历完分支后一次删除这个分支在哈希表中的路径和，最后得到结果。

解题代码

class Solution {
public:
    unordered_map<int, int> mp; //记录路径和及条数
    int dfs(TreeNode* root, int sum, int last)
    {   //last为到上一层为止的累加和
        if(root == NULL) //空结点直接返回
            return 0;
        int res = 0;
        int temp = root->val + last; //到目前结点为止的累加和
        if(mp.find(temp - sum) != mp.end())  //如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支
            res += mp[temp - sum]; //加上有的路径数
        mp[temp]++; //增加该次路径和
        res += dfs(root->left, sum, temp); //进入子结点
        res += dfs(root->right, sum, temp);
        mp[temp]--; //回退该路径和，因为别的树枝不需要这边存的路径和
        return res;
    }
    int FindPath(TreeNode* root, int sum) { 
        mp[0] = 1; //路径和为0的有1条
        return dfs(root, sum, 0);
    }
};

复杂度分析

时间复杂度：一次深度优先，因此时间复杂度为$O(N)O(N)$

空间复杂度：深度优先的栈深度为n，因此空间复杂度为$O(N)O(N)$