【牛客 - 剑指offer】JZ84 二叉树中和为某一值的路径(三)

---

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 树 - JZ84 二叉树中和为某一值的路径(三)

题目

解决方案

方案一 深度优先搜索 dfs

dfs思路

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

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

思路

• 既然要找所有路径上节点和等于目标值的路径个数，那首先，得找到起点。题目中不要求一定要从根节点开始，也不要求一定要在叶子节点结束，所以任意起点都有可能成为起点，可以使用前序遍历遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。

FindPath(root.left, sum);
FindPath(root.right,sum);
1
2

• 查找路径的时候，需要往下遍历，因此还是按照前序遍历的方式遍历该子树，在遍历过程中遇到一个节点，sum相应的减少，若往下的一个节点值正好等于剩下的sum，则找到了个情况

dfs(root.left, sum-root.val);
dfs(root.right, sum-root.val);
1
2

• FindPath()方法用于遍历所有节点，让其作为根节点，检查是否有合适的路径

• dfs()方法，针对于每一个子树，检查以该节点为根的子树上是否有满足条件的

代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param root TreeNode类
     * @param sum  int整型
     * @return int整型
     */
    private int res = 0;

    public int FindPath(TreeNode root, int sum) {
        // write code here
        if (root == null) {
            return res;
        }
        //查询以某节点为根的路径数
        dfs(root, sum);

        //以其子节点为新根
        FindPath(root.left, sum);
        FindPath(root.right, sum);
        return res;
    }


    //dfs查询以某节点为根的路径数
    public void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        if (sum == root.val) {
            //System.out.println("root.val" + root.val);
            res++;
        }
        dfs(root.left, sum - root.val);
        dfs(root.right, sum - root.val);
    }
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51

dfs个人总结

我自己认为，dfs的代码比较难写，但是在看到答案以后又觉得很简单，真正调试起来一层一层的递归，看得头都大了，所以应对dfs最好的方法就是Debug，可以把递归过程看得很清楚，有时侯，手速快了点，断点少了点，就跳过去了，那就从头再Debug一遍吧，Debug的断点我建议尽可能多打，这样能避免错过一些重要的过程

方案二 哈希表 HashMap

哈希表思路

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

上面的dfs思路每一个节点都要作为子树，按照前序遍历的顺序遍历一次，有的节点有被重复计算

在进入以某个节点为根的子树中，向其中添加到该节点为止的路径，和进入哈希表中，相当于每次分支下都有前面各种路径和。

如果从根节点开始到当前节点的累加和减去sum，在哈希表中出现过，则说明这条路径上前半段和等于到当前节点的累加和减去sum，

代码

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

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

个人总结

虽然方案一的效率没有方案二高，但是方案一比较容易理解，方案二中，我认为，比较关键的代码是：

//如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支
if(mp.containsKey(temp - sum))
    //加上有的路径数
    res += mp.get(temp - sum);
1
2
3
4

在遍历 1 2 5 -1 这条线的时候，temp=7，但是除去根节点1以后，就是我们要找的满足条件的一条路线，所以，如果map中存在一条，前面路径和是1的路径，则结果计数就可以+1

我这么说感觉也很苍白无力，需要自己动手debug一下，就比较清楚了