Binary Tree Path Sum II
update Jul 14, 2017 20:14
Your are given a binary tree in which each node contains a value. Design an algorithm to get all paths which sum to a given value. The path does not need to start or end at the root or a leaf, but it must go in a straight line down.
Example
Given a binary tree:
1
/ \
2 3
/ /
4 2
for target = 6, return
[
[2, 4],
[1, 3, 2]
]Basic Idea:
这道题和leetcode上的 Path Sum III 其实很接近，但是这道题更加要求输出所有的路径。在前面的那篇文章中我们使用了两个函数两层递归的方式，但是这样的方法相对复杂。学习了九章算法之后，我发现我们可以使用一种更加通用而且易于理解的方法：
整个代码的框架是一个求所有path并返回的程序，只是在我们到达每个node之后，对当前的path进行一次循环，考虑所有在当前位置结束的path，如果 sum == target ，则将这一段path加入res。具体地，对于Java，我们可以用 res.add(new ArrayList<Integer>(path.subList(i, path.size()))) , 在Python中更加方便，直接res.append(path[i:])。
Java Code：
public class Solution {
/**
* @param root the root of binary tree
* @param target an integer
* @return all valid paths
*/
// 先按照正常方法traverse，在path中跟踪路径，只是每次到新的node，for循环当前
// path，找以此node结尾的path中是否有满足要求的，若有，加入res
public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
List<List<Integer>> res = new ArrayList<>();
helper(root, new ArrayList<Integer>(), res, target);
return res;
}
private void helper(TreeNode node, List<Integer> path, List<List<Integer>> res, int target) {
if (node == null) return;
path.add(node.val);
for (int i = 0; i < path.size(); ++i) {
int sum = 0;
for (int j = i; j < path.size(); ++j) {
sum += path.get(j);
}
if (sum == target) {
res.add(new ArrayList<Integer>(path.subList(i, path.size())));
}
}
helper(node.left, path, res, target);
helper(node.right, path, res, target);
path.remove(path.size() - 1);
}
}Python Code:
class Solution:
# @param {TreeNode} root the root of binary tree
# @param {int} target an integer
# @return {int[][]} all valid paths
def binaryTreePathSum2(self, root, target):
def helper(root, path, res, target):
if not root: return
path.append(root.val)
for i in range(len(path)):
sum = 0
for j in range(i, len(path)):
sum += path[j]
if sum == target:
res.append(path[i:])
helper(root.left, path, res, target)
helper(root.right, path, res, target)
del path[-1]
res = []
helper(root, [], res, target)
return resupdate Dec 21, 2017 23:36
Update
时隔数月，发现之前的写法其实并没有领会九章算法所授的分治法的道理。在这里重新写了一个新方法的 Java solution。
在这次的写法中，严格按照九章分治法的思路，对于一个关于root的问题，我们将其化解为一个关于 root.left 和 root.right 的同样的问题，再利用左右的返回值求出关于 root 的解。
具体地，我们通过左右子树递归的返回值得到从 左右节点 出发向下的所有路径，然后在每个这种路径的前面都加上 root.val，再加上一个只含有 root.val 的路径，我们就得到了从 root 开始向下的所有路径。这样就完成了一个分治算法。在得到从root开始向下的所有路径之后，我们循环判断这些路径中是否有满足条件的，若有，则将其副本加入 res;
public class Solution {
/*
* @param root: the root of binary tree
* @param target: An integer
* @return: all valid paths
*/
// 从下往上
public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
helper(root, target, res);
return res;
}
// return all paths go down from this node, 每次检查从该 root 开始有无满足要求的path
private List<List<Integer>> helper(TreeNode root, int target, List<List<Integer>> res) {
List<List<Integer>> paths = new ArrayList<>();
if (root == null) return paths;
List<List<Integer>> leftPaths = helper(root.left, target, res);
List<List<Integer>> rightPaths = helper(root.right, target, res);
paths.addAll(leftPaths);
paths.addAll(rightPaths);
// 插入一个空链表，这样将root加在每个路径前面之后，这个链表就表示一条只有
// root一个node的路径。这也是递归最先开始有记录的地方，就是left和right都是
// 空，然后插入一个空链表，再其头部加上root，成为第一条路径.
paths.add(new LinkedList<Integer>());
for (List<Integer> path : paths) path.add(0, root.val);
// 此时 paths 中就包含了所有从当前 root 开始向下的路径, 然后我们开始检查每
// 条路径的和，如果满足要求，则把次path的副本加入res（之所以是副本，是因为随着
// 递归的进行，该path还会被修改）
for (List<Integer> path : paths) {
int sum = 0;
for (int n : path) sum += n;
if (sum == target) res.add(new ArrayList<>(path));
}
return paths;
}
}update Feb 19 2019, 17:27
Update: 最直观的解
重做此题，感觉最直观最简单的解法任然是从上到下传一个path数组，每一层先用两层for loop计算有多少从上到下且以当前node截止的满足条件的path，加入res。
public class Solution {
/*
* @param root: the root of binary tree
* @param target: An integer
* @return: all valid paths
*/
public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
dfs(root, new ArrayList<>(), res, target);
return res;
}
private void dfs(TreeNode root, List<Integer> path, List<List<Integer>> res, int target) {
path.add(root.val);
for (int i = 0; i < path.size(); ++i) {
int sum = 0;
for (int j = i; j < path.size(); ++j) {
sum += path.get(j);
}
if (sum == target) res.add(new ArrayList<>(path.subList(i, path.size())));
}
if (root.left != null) dfs(root.left, path, res, target);
if (root.right != null) dfs(root.right, path, res, target);
path.remove(path.size() - 1);
}
}Last updated