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

题目的主要信息：

• 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum
• 路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点，如下图所示：

举一反三：

学习完本题的思路你可以解决如下题目：

JZ82. 二叉树中和为某一值的路径(一)

JZ34. 二叉树中和为某一值的路径(二)

方法一：两次遍历（推荐使用）

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点啊，但是我们不知道起点究竟在哪里，而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。

//以其子结点为新根
FindPath(root.left, sum); 
FindPath(root.right, sum);

查找路径的时候呢，也需要往下遍历，因此还可以继续前序遍历该子树，在遍历的过程遇到一个节点，sum相应减少，若是到最后往下的一个节点值正好等于剩下的sum，则找到一种情况。

//符合目标值
if(sum == root.val) 
    res++;

因为前序递归的次序是根左右，因此一定是往下找的路径，不会往上回溯。

//进入子节点继续找
dfs(root.left, sum - root.val); 
dfs(root.right, sum - root.val);

具体做法：

• step 1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，如果该节点为空则返回。
• step 2：然后递归遍历这棵树每个节点，每个节点都需要这样操作。
• step 3：在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。
• step 4：剩余的sum等于当前节点值则找到一种情况。

Java实现代码：

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

C++实现代码：

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

Python实现代码：

class Solution:
    def __init__(self):
        self.res = 0
        
    #dfs查询以某节点为根的路径数
    def dfs(self, root: TreeNode, sum: int):
        if root is None:
            return
        #符合目标值
        if sum == root.val: 
            self.res += 1
        #进入子节点继续找
        self.dfs(root.left, sum - root.val) 
        self.dfs(root.right, sum - root.val)
    
    def FindPath(self , root: TreeNode, sum: int) -> int:
        #为空则返回
        if root is None:
            return self.res
        #查询以某节点为根的路径数
        self.dfs(root, sum) 
        #以其子节点为新根
        self.FindPath(root.left, sum); 
        self.FindPath(root.right, sum)
        return self.res

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，其中$nn$为二叉树的结点数，两层dfs嵌套递归
• 空间复杂度：$O(n)O(n)$，每层dfs最深递归栈都只有$nn$

方法二：一次遍历+哈希表（扩展思路）

知识点：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

两次遍历有些浪费，我们看看可不可以一次遍历解决：

在进入以某个结点为根的子树中，向其中添加到该节点为止的路径和进入哈希表中，相当于每次分枝下都有前面各种路径和。如果从根节点开始到当前节点的累加和减去sum，在哈希表中出现过，则说明这条路径上前半段和等于到当前节点的累加和减去sum，那后半段不就等于sum了吗？因此我们只需要在计算的时候加上哈希表中这样值的路径数就可以了。

具体做法：

• step 1：准备一个哈希表，首先放入到根节点为止的路径和为0，路径跳数为1.然后从根节点开始递归遍历二叉树。
• step 2：在递归的时候，我们将需要找的目标和sum与到上一层为止的累加和一并放入函数参数中，跟随递归，遇到空节点则返回。
• step 3：累加到当前节点为止的路径和，如果该累加和减去sum在哈希表中出现过，相当于减去最前面出现过这个差值的一段，到该节点为止就是sum，我们加上这样的路径数。
• step 4：继续递归子节点，累加这样的路径数。进入其他分支前要回溯哈希表中刚刚添加的路径和，因为我们每次只要直属于这条路径上的值，其他路径的就不要。

图示：

Java实现代码：

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

    public int FindPath (TreeNode root, int sum) {
        //路径和为0的有1条
        mp.put(0, 1); 
        return dfs(root, sum, 0);
    }
}

C++实现代码：

class Solution {
public:
    //记录路径和及条数
    unordered_map<int, int> mp; 
    //last为到上一层为止的累加和
    int dfs(TreeNode* root, int sum, int last){ 
        //空结点直接返回
        if(root == NULL) 
            return 0;
        int res = 0;
        //到目前结点为止的累加和
        int temp = root->val + last; 
        //如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支
        if(mp.find(temp - sum) != mp.end())  
            //加上有的路径数
            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) { 
        //路径和为0的有1条
        mp[0] = 1; 
        return dfs(root, sum, 0);
    }
};

Python实现代码：

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

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为二叉树的结点数，遍历一次二叉树，哈希表的操作都是$O(1)O(1)$
• 空间复杂度：$O(n)O(n)$，哈希表大小及递归栈最大为$nn$