二叉树路径总和系列问题
作者：Grey
原文地址：
LeetCode 112. 路径总和
定义递归函数
boolean process(TreeNode node, int preSum, int target)
递归含义表示：从 node 节点一直到树的叶子节点，preSum 表示 node 之前的节点之和，target 表示目标值。主函数调用
public boolean hasPathSum(TreeNode root, int targetSum) {
return process(root, 0, targetSum);
}
就是要的答案。
接下来是递归函数的 base case，容易得到
if (node == null) {
// 空节点自然返回false，即永远得不到 target 值
return false;
}
if (node.left == null && node.right == null) {
// node 是叶子节点
// 可以结算了，前面得到的值 + 当前节点值 如果符合目标值，就返回 true
// 否则返回 false
return preSum + node.val == target;
}
接下来是普遍情况，当前节点往右走，或者当前节点往左走，如果任何一个满足条件，就返回 true 表示满足，否则返回 false
return process(node.left, preSum + node.val, target) || process(node.right, preSum + node.val, target);
完整代码如下
public boolean hasPathSum(TreeNode root, int targetSum) {
return process(root, 0, targetSum);
}
// 从 某个节点到 叶子节点，是否可以累计得到某个值（targetSum), 之前的值是 preSum
public boolean process(TreeNode node, int preSum, int target) {
if (node == null) {
return false;
}
if (node.left == null && node.right == null) {
// node 是叶子节点
return preSum + node.val == target;
}
return process(node.left, preSum + node.val, target) || process(node.right, preSum + node.val, target);
}
LeetCode 113. 路径总和 II
定义递归函数
void process(TreeNode node, int preSum, List<Integer> path, int targetSum, List<List<Integer>> result)
递归含义表示：从 node 节点一直到树的叶子节点，preSum 表示 node 之前的节点之和，targetSum 表示目标值，path 记录之前的节点轨迹，result 用于收集所有满足条件的 path，主函数调用：
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> path = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
// 从 root 到叶子节点
// preSum 初始为 0，path 和 result 都初始为空
process(root, 0, path, targetSum, result);
return result;
}
递归函数的 base case 如下：
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
// 叶子节点
if (preSum + node.val == targetSum) {
path.add(node.val);
result.add(path);
}
return;
}
说明：针对叶子节点（即：node.left == null && node.right == null），如果满足条件preSum + node.val == targetSum，则找到一条满足条件的路径，使得结果之和等于目标值，此时 result 开始收集result.add(path)。
接下来是普遍情况，为了避免 path 在走左侧和走右侧的时候被污染，所以拷贝出两个 path 的副本来进行递归调用
// 走左侧，用copy1
List<Integer> copy1 = new ArrayList<>(path);
// 走右侧，用copy2
List<Integer> copy2 = new ArrayList<>(path);
copy1.add(node.val);
copy2.add(node.val);
接下来调用递归函数
process(node.left, preSum + node.val, copy1, targetSum, result);
process(node.right, preSum + node.val, copy2, targetSum, result);
完整代码如下
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> path = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
process(root, 0, path, targetSum, result);
return result;
}
public void process(TreeNode node, int preSum, List<Integer> path, int targetSum, List<List<Integer>> result) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
// 叶子节点
if (preSum + node.val == targetSum) {
path.add(node.val);
result.add(path);
}
return;
}
List<Integer> copy1 = new ArrayList<>(path);
List<Integer> copy2 = new ArrayList<>(path);
copy1.add(node.val);
copy2.add(node.val);
process(node.left, preSum + node.val, copy1, targetSum, result);
process(node.right, preSum + node.val, copy2, targetSum, result);
}
LeetCode 437. 路径总和 III
这一题和上一个 Path Sum II 问题最大的区别是：这里不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。返回的结果也只需要给出路径的条数，不需要给出具体的路径情况。
定义递归函数
int process(TreeNode node, int targetSum, long preSum, HashMap<Long, Integer> preSumMap)
递归含义表示：从 node 到结尾，前面累计的结果是 preSum，前面组成的路径中，每个路径之和的结果有多少种，存在 preSumMap 中（即：preSum(i, j) 表示 前面路径的累加和为 i 的路径有 j 种），返回得到 targetSum 的路径数有多少种。
所以主函数调用
process(root, targetSum, 0, preSumMap);
即为答案，先看递归函数完整代码
// 返回方法数
// 从 node 到结尾，前面累计的结果是 preSum，前面组成的路径中，每个路径之和的结果有多少种，存在 preSumMap
// preSum(i,j) 表示 前面路径的累加和为 i 的路径有 j 种
public int process(TreeNode node, int targetSum, long preSum, HashMap<Long, Integer> preSumMap) {
if (node == null) {
return 0;
}
long all = preSum + node.val;
int ans = 0;
if (preSumMap.containsKey(all - targetSum)) {
// 说明之前有路径可以得到
ans = preSumMap.get(all - targetSum);
}
// 登记当前结果到preSumMap中
if (!preSumMap.containsKey(all)) {
preSumMap.put(all, 1);
} else {
preSumMap.put(all, preSumMap.get(all) + 1);
}
ans += process(node.left, targetSum, all, preSumMap);
ans += process(node.right, targetSum, all, preSumMap);
// 清理现场
if (preSumMap.get(all) == 1) {
preSumMap.remove(all);
} else {
preSumMap.put(all, preSumMap.get(all) - 1);
}
return ans;
}
其中
if (node == null) {
return 0;
}
是 base case，空树，返回 0 种方法数，
接下来:
long all = preSum + node.val;
int ans = 0;
if (preSumMap.containsKey(all - targetSum)) {
// 说明之前有路径可以得到
ans = preSumMap.get(all - targetSum);
}
表示，想得到目标值 targetSum，而当前的累加和是 all，说明 preSumMap 中必须存着累加和为(all - targetSum)的记录。
假设之前(all - targetSum)结果的路径有 n 条，那么结果至少是 n。
接下来：
// 登记当前结果到preSumMap中
if (!preSumMap.containsKey(all)) {
preSumMap.put(all, 1);
} else {
preSumMap.put(all, preSumMap.get(all) + 1);
}
表示登记当前之和为 all 的记录到 preSumMap 中，再接下来:
ans += process(node.left, targetSum, all, preSumMap);
ans += process(node.right, targetSum, all, preSumMap);
表示去左右树收集答案，累加到 ans 中，最后：
// 清理现场
if (preSumMap.get(all) == 1) {
preSumMap.remove(all);
} else {
preSumMap.put(all, preSumMap.get(all) - 1);
}
递归函数清理现场，常规操作。
特别注意，由于递归函数中
long all = preSum + node.val;
int ans = 0;
if (preSumMap.containsKey(all - targetSum)) {
// 说明之前有路径可以得到
ans = preSumMap.get(all - targetSum);
}
这里判断条件是preSumMap.containsKey(all - targetSum)，而当 preSumMap 一个元素也没有的时候，可以组成和为 0L 的路径，所以，在主函数调用的时候，需要增加一句
preSumMap.put(0L, 1);
完整代码如下
public int pathSum(TreeNode root, int targetSum) {
HashMap<Long, Integer> preSumMap = new HashMap<>();
// 累加和为0的情况，默认就有一种了（空树）
preSumMap.put(0L, 1);
return process(root, targetSum, 0, preSumMap);
}
// 返回方法数
// 从 node 到结尾，前面累计的结果是 preSum，前面组成的路径中，每个路径之和的结果有多少种，存在 preSumMap
// preSum(i,j) 表示 前面路径的累加和为 i 的路径有 j 种
public int process(TreeNode node, int targetSum, long preSum, HashMap<Long, Integer> preSumMap) {
if (node == null) {
return 0;
}
long all = preSum + node.val;
int ans = 0;
if (preSumMap.containsKey(all - targetSum)) {
// 说明之前有路径可以得到
ans = preSumMap.get(all - targetSum);
}
// 登记当前结果到preSumMap中
if (!preSumMap.containsKey(all)) {
preSumMap.put(all, 1);
} else {
preSumMap.put(all, preSumMap.get(all) + 1);
}
ans += process(node.left, targetSum, all, preSumMap);
ans += process(node.right, targetSum, all, preSumMap);
// 清理现场
if (preSumMap.get(all) == 1) {
preSumMap.remove(all);
} else {
preSumMap.put(all, preSumMap.get(all) - 1);
}
return ans;
}