前言
路径总和相关题目是将回溯和二叉树融合到一起的应用，今天就主要感受一下回溯在二叉树中的使用。
题目
//给定一个二叉树，它的每个结点都存放着一个整数值。
//
// 找出路径和等于给定数值的路径总数。
//
// 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
//
// 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
//
// 示例：
//
// root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
//
// 10
// / \
// 5 -3
// / \ \
// 3 2 11
// / \ \
//3 -2 1
//
//返回 3。和等于 8 的路径有:
//
//1. 5 -> 3
//2. 5 -> 2 -> 1
//3. -3 -> 11
//
题目拆解
其实应该吧路径总和三道题放到一起来做，递进的感觉会更强，但是今天时间来不及了，就姑且先把第三题列出来，明天在写这个系列。
首先分析分析一下这道题的根本诉求，是求总共有多少种情况，一半这种要求接，一共有多少种路啊，一共有多少种组合啊，一共有多少种...什么的，大概率是回溯没跑了，比如经典的八王后，所以，先把核心的算法思路明确，这道题是一个回溯题。
确认回溯了，那就要进行剪枝和递归，这道题的节点取值范围正负数都有，求和和目标值相同，那么剪枝的判断也就只剩下节点为空的之后，就不再往下走了。
剩下的就是回溯的具体思路，虽然是在二叉树中的应用，但也不要太慌张，如果是一维的数组，这个题下我们怎么处理呢？无非也是这么几步
- 1、从头开始往后加，刚好加到目标值了，记录一个值，然后不要停下继续往下走，因为可能存在1，2，3，-1，1这样的情况，所以达到目标值也要继续走下去。
- 2、走到头，一节一节往回退，在探索别的路线。
- 3、退到头了，往前进一步。
- 4、循环1-3的步骤。
二叉树和普通的回溯区别就在于这第二步，二叉树还是有探索空间的，所以往回退一步的时候，要换个方向继续走下去。
思路分析到这里，我写出了第一版代码
代码错误版本
public void dfs(TreeNode root, int sum, int curr) {
if (root == null) return;
int currSum = curr - root.val;
if (currSum == 0) {
count++;
} else {
dfs(root.left, sum, currSum);
dfs(root.right, sum, currSum);
}
dfs(root.left, sum, sum);
dfs(root.right, sum, sum);
}
其实思路看起来也没啥问题，每一层得到一个数，我就减一下，减到0了，就算到了终点，结果++，但是少思考了两个点，一个是上面说的不要停下，导致结果变少；另外一个，就是回溯的状态清除有误，回复为初始状态，导致最后的计算结果增多；
思考一会之后，发现了一个本质的问题，我没有办法区分1，2，3 和 1，2，3，-1，1；也没有办法区分是从那个节点开始计算的，这条链路上加了多少个点，看过了多少风景，我都不知道，那么实现起来就会变得很困难，所以这时候也转化了一下思路，需要引入动态规划了。
我们需要维护一个状态，来标记每一个节点前的路径和结果，白话就是走到一个节点了，前面的节点有多少种累加结果？举个例子
1，2，3，4，5
在3节点的位置，他前面的路径状态一共有3种，1+2 = 3；0 + 2= 2，0 + 0 = 0；
实际上我们也不关心是谁加谁等于谁，我们关心的只是和为3有几种情况，和为2有几种情况，所以这个状态只需要存储所有前缀和及这个前缀和对应的数量即可。参考了几位大神的代码，最终版本的代码如下
代码
class Solution {
private int count = 0;
public int pathSum(TreeNode root, int sum) {
Map<Integer, Integer> sum2Count = new HashMap<>();
sum2Count.put(0, 1);
dfs(root, sum2Count, sum, 0);
return count;
}
public void dfs(TreeNode root, Map<Integer, Integer> sum2Count, int sum, int ssum) {
// 剪枝
if(root == null) return;
// 记录当前结果
int currSum = ssum + root.val;
// 累加到结果中
count += sum2Count.getOrDefault(currSum - sum, 0);
// 将当前结果添加到前缀和中
sum2Count.put(currSum, sum2Count.getOrDefault(currSum, 0) + 1);
// 不要停,往下走
dfs(root.left, sum2Count, sum, currSum);
// 回溯到这里,换个方向继续走
dfs(root.right, sum2Count, sum, currSum);
// 清空状态,回到上一层
sum2Count.put(currSum, sum2Count.get(currSum) - 1);
}
总结
总结一下这个题解，今天难得题解写的不是很顺畅，写完以后读起来，感觉也不是很便于其他同学去理解这道题，更多还是自己对题目本身的设想，不够有结构和建设性，这点需要再优化一下。
网友评论