[Algorithm]Get Paths with Given Sum in Binary Tree

根据target得到所有path，path可以在任意一个节点开始和结束。和path with max sum类似，不过我们每次递归要返回的是子树里的所有path，为了避免不必要的计算，我们发挥所有path的时候也同时返回所有对应path的sum，所以我们新定义一个类result。在一个节点的时候，我们先递归左子树和右子树找到左子树和右子树中的的所有path，然后进行一下三种操作：

• 首先看当前node.val是不是等于target，如果是的话，当前node加入结果集，path只有当前node
• 然后看当前node和左子树return回来的每一条path能不能组成sum == target的path，能的话加入结果集
• 当前node和右子树return回来的每一条path能不能组成sum == target的path，能的话加入结果集
• 最后看左子树的每一条path和右子树的每一条path和当前node能不能组成sum == target的path，能的话加入结果集

不考虑加入结果集的时间，由于return回来的子树的path数为O(N^2)，因为两个node可以决定一条path，前三个都可以在O(N^2)时间完成，最后一步归根到底就是Two Sum的问题，也可以在O(N^2)时间完成。加入结果的时间取决于结果的多少k，path长度O(log n)，所以加入结果集的时间为O(k log n)。

最后注意把左边所有path右边path和当前node merge一下，return所有已当前node为root的subtree的所有path，记得加上当前node自己。这一步也是O(N^2)的，所以T(N) = 2T(N/2) + O(N^2)，根据master theorem，时间复杂度为O(N^2)。计算所需要的空间，所有path数量是N^2，因为两个node可以决定一条path，path的长度是O(log N)，所以空间复杂度是O(N^2 * log N)，代码如下：

	public class GetPaths {
	private class Result {
	private ArrayList<ArrayList<Integer>> paths;
	private ArrayList<Integer> sums;
	public Result() {
	paths = new ArrayList<ArrayList<Integer>>();
	sums = new ArrayList<Integer>();
	}
	public Result(ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> sums) {
	this.paths = paths;
	this.sums = sums;
	}
	}
	private ArrayList<ArrayList<Integer>> res;
	public ArrayList<ArrayList<Integer>> getPaths(TreeNode root, int target) {
	res = new ArrayList<ArrayList<Integer>>();
	getPathsInSubTree(root, target);
	return res;
	}
	private Result getPathsInSubTree(TreeNode node, int target) {
	if (node == null)
	return new Result();
	Result left = getPathsInSubTree(node.left, target);
	Result right = getPathsInSubTree(node.right, target);
	ArrayList<Integer> leftSums = left.sums;
	ArrayList<Integer> rightSums = right.sums;
	ArrayList<ArrayList<Integer>> leftPaths = left.paths;
	ArrayList<ArrayList<Integer>> rightPaths = right.paths;
	//find qualified path
	//current node
	if (node.val == target) {
	ArrayList<Integer> temp = new ArrayList<Integer>();
	temp.add(node.val);
	res.add(temp);
	}
	//curr node and path from left subtree
	int leftLen = leftSums.size();
	for (int i = 0; i < leftLen; i++) {
	if (leftSums.get(i) == target - node.val) {
	ArrayList<Integer> temp = new ArrayList<Integer>(leftPaths.get(i));
	temp.add(node.val);
	res.add(temp);
	}
	}
	//curr node and path from right subtree
	int rightLen = rightSums.size();
	for (int i = 0; i < rightLen; i++) {
	if (rightSums.get(i) == target - node.val) {
	ArrayList<Integer> temp = new ArrayList<Integer>(rightPaths.get(i));
	temp.add(node.val);
	res.add(temp);
	}
	}
	//curr and path from left and path from right, actually two sum problem
	HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
	for (int i = 0; i < rightLen; i++) {
	if (!map.containsKey(rightSums.get(i))) {
	ArrayList<Integer> temp = new ArrayList<Integer>();
	temp.add(i);
	map.put(rightSums.get(i), temp);
	} else {
	map.get(rightSums.get(i)).add(i);
	}
	}
	for (int i = 0; i < leftLen; i++) {
	if (map.containsKey(target - node.val - leftSums.get(i))) {
	ArrayList<Integer> indexes = map.get(target - node.val - leftSums.get(i));
	int size = indexes.size();
	for (int j = 0; j < size; j++) {
	ArrayList<Integer> rightPath = rightPaths.get(indexes.get(j));
	//merge left curr and right
	ArrayList<Integer> temp = new ArrayList<Integer>(leftPaths.get(i));
	temp.add(node.val);
	for (int k = rightPath.size() - 1; k >= 0; k--)
	temp.add(rightPath.get(k));
	res.add(temp);
	}
	}
	}
	//merge paths and return
	for(int i = 0; i < leftLen; i++) {
	leftSums.set(i, leftSums.get(i) + node.val);
	leftPaths.get(i).add(node.val);
	}
	for (int i = 0; i < rightLen; i++) {
	rightSums.set(i, rightSums.get(i) + node.val);
	rightPaths.get(i).add(node.val);
	}
	ArrayList<ArrayList<Integer>> retPaths = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> retSums = new ArrayList<Integer>();
	for(int i = 0; i < leftLen; i++) {
	retPaths.add(leftPaths.get(i));
	retSums.add(leftSums.get(i));
	}
	for (int i = 0; i < rightLen; i++) {
	retPaths.add(rightPaths.get(i));
	retSums.add(rightSums.get(i));
	}
	ArrayList<Integer> currPath = new ArrayList<Integer>();
	currPath.add(node.val);
	retPaths.add(currPath);
	retSums.add(node.val);
	return new Result(retPaths, retSums);
	}
	//for test use, serialize path
	public String serialize(ArrayList<ArrayList<Integer>> paths) {
	int size = paths.size();
	String res = "#";
	for (int i = 0; i < size; i++) {
	int len = paths.get(i).size();
	for (int j = 0; j < len; j++) {
	if (j == 0)
	res += paths.get(i).get(j);
	else
	res += "," + paths.get(i).get(j);
	}
	res += "#";
	}
	return res;
	}
	public static void main(String[] args) {
	test1();
	test2();
	test3();
	}
	//test cases
	private static void test1() {
	TreeNode root = new TreeNode(1);
	GetPaths g = new GetPaths();
	System.out.println(g.serialize(g.getPaths(null, 0)));
	System.out.println(g.serialize(g.getPaths(root, 1)));
	}
	private static void test2() {
	TreeNode root = new TreeNode(1);
	root.left = new TreeNode(2);
	root.right = new TreeNode(3);
	root.left.right = new TreeNode(4);
	root.left.left = new TreeNode(7);
	root.left.left.left = new TreeNode(10);
	root.right.right = new TreeNode(5);
	root.right.left = new TreeNode(6);
	root.right.right.right = new TreeNode(1);
	root.right.left.left = new TreeNode(-2);
	root.left.left.right = new TreeNode(-3);
	root.left.left.right.right = new TreeNode(0);
	GetPaths g = new GetPaths();
	System.out.println(g.serialize(g.getPaths(root, 10)));
	}
	private static void test3() {
	TreeNode root = new TreeNode(-3);
	root.left = new TreeNode(7);
	root.right = new TreeNode(6);
	root.left.left = new TreeNode(4);
	root.left.right = new TreeNode(-2);
	root.right.right = new TreeNode(5);
	root.left.left.left = new TreeNode(12);
	root.left.left.left.right = new TreeNode(0);
	root.left.right.right = new TreeNode(10);
	root.right.right.left = new TreeNode(-8);
	root.right.right.right = new TreeNode(9);
	root.right.right.left.left = new TreeNode(17);
	root.right.right.right.right= new TreeNode(20);
	GetPaths g = new GetPaths();
	System.out.println(g.serialize(g.getPaths(root, 21)));
	System.out.println(g.serialize(g.getPaths(root, 32)));
	}
	}

view raw get path II.java hosted with ❤ by GitHub