学步园

二叉树是面试里常考的一类数据结构，其中有一类寻找路径问题很有意思。目前见过两种类型题目，都是先给出一个和，然后要求打印出节点值之和与此相等的路径问题。

1. Given a binary tree and a number, print all the root-to-leaf paths such that adding up all the values along the path equals the given number.

这个题目比较简单，因为要求所求的路径必须从根节点到叶节点。注意这里所说的二叉树并不是二叉搜索树。此外，如果面试时遇到这个题目，首先应该问面试官确定二叉树的节点值是否都是正数。如果有全为正数这个限制，那么设计的算法可以有效进行剪枝——如果当前路径的和已经超过了目标和，则可以停止继续搜索了。

搜索时记录当前路径上的所求节点以及当前和。

搜索分为两种情况：

1）遇到叶节点：检查是否路径的和与目标和相等，若相等则为所求；

2）遇到非叶节点：对左右两个分支递归调用搜索函数。

	@SuppressWarnings("unchecked")
	public static void findPaths(TreeNode root, int sum, int curSum,
			ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {
		if (root == null)
			return;

		path.add(root.val);
		curSum += root.val;
		// leaf node
		if (root.left == null && root.right == null) {
			if (curSum == sum) {
				paths.add(path);
			}
		}
		// non-leaf node
		else {
			findPaths(root.left, sum, curSum, (ArrayList<Integer>) path.clone(),
						paths);

			findPaths(root.right, sum, curSum, path, paths);
		}
	}

	public static void main(String args[]) {
		TreeNode root = new TreeNode(10);
		root.left = new TreeNode(8);
		root.right = new TreeNode(2);
		root.left.left = new TreeNode(3);
		root.left.right = new TreeNode(5);
		root.right.left = new TreeNode(2);

		ArrayList<Integer> path = new ArrayList<Integer>();
		ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();

		findPaths(root, 21, 0, path, paths);
		System.out.println(paths);

		path.clear();
		paths.clear();
		findPaths(root, 23, 0, path, paths);
		System.out.println(paths);

		path.clear();
		paths.clear();
		findPaths(root, 14, 0, path, paths);
		System.out.println(paths);
	}

为了使得这里的算法能够有较好的适用性，这里假设没有全为正数这个条件，而且希望能够把所有路径都收集起来，而不是遇到一条所求路径就打印出来。我这里将所有的所求路径都放到了一个二维数组链表容器里。

注意这里递归调用时我对path使用了clone函数，表明是传值而非传引用。本质是利用了回溯的思想，保证即使路径没有找到，path最终不会被修改而影响同一个函数内的下一次递归调用。时间复杂度是O(N*logN)，因为每个节点遍历了一遍用了O(N)时间，而对于每个节点，传递path或者说打印path都需要O(logN)时间。

2. You are given a binary tree in which each node contains a value Design an algorithm to print all paths which sum up to that value Note that it can be any path in the tree 

- it does not have to start at the root.

	@SuppressWarnings("unchecked")
	public static void findPaths(TreeNode node, int sum, int curSum,
			ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {
		if (node == null) {
			return;
		}

		path.add(node.val);
		curSum += node.val;

		// the path can end with the current node
		if (sum == curSum) {
			paths.add(path);
		}

		// continue the current path, or start another path from the next node
		if (node.left != null) {
			// continue the current path
			findPaths(node.left, sum, curSum,
					(ArrayList<Integer>) path.clone(), paths);
			// start another new path from the left child node
			findPaths(node.left, sum, 0, new ArrayList<Integer>(), paths);
		}
		if (node.right != null) {
			// continue the current path
			findPaths(node.right, sum, curSum,
					(ArrayList<Integer>) path.clone(), paths);
			// start another new path from the right child node
			findPaths(node.right, sum, 0, new ArrayList<Integer>(), paths);
		}
	}

不过测试时发现这里存在重复递归，从而生成了冗余的路径。原因是我在进行对当前路径扩展的递归调用和生成新路径的递归调用使用的同一个函数接口。举个例子说明，假设输入的二叉树至少有3层，在根节点搜索时，会产生两个搜索分支：

1.1）尝试让子节点延续以根节点为起点的路径；

1.2）尝试以子节点为起点的新路径。

而在子节点搜索时，对于分支1.1，会再产生两个搜索分支：

2.1）尝试让孙子节点延续以根节点为起点的路径；

2.2）尝试以孙子节点为起点的新路径。

对于分支1.2，也会产生两个搜索分支：

2.3) 尝试让孙子节点延续以父节点为起点的路径；

2.4) 尝试以孙子节点为起点的新路径。

可以发现，分支2.2和2.4完全相同，属于重复递归。解决的方法是使用两个不同的搜索函数：一个负责搜索所有可能路径，另一个只负责通过延续当前路径来搜索。

	public static void findPaths(TreeNode node, int sum,
			ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {
		if (node == null) {
			return;
		}

		// continue the current path
		continueCurPath(node, sum, 0, path, paths);

		// start a new path from the next node
		findPaths(node.left, sum, new ArrayList<Integer>(), paths);
		findPaths(node.right, sum, new ArrayList<Integer>(), paths);
	}

	@SuppressWarnings("unchecked")
	public static void continueCurPath(TreeNode node, int sum, int curSum,
			ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {
		if (node == null) {
			return;
		}

		curSum += node.val;
		path.add(node.val);

		if (curSum == sum) {
			paths.add(path);
		}

		continueCurPath(node.left, sum, curSum,
				(ArrayList<Integer>) path.clone(), paths);
		continueCurPath(node.right, sum, curSum,
				(ArrayList<Integer>) path.clone(), paths);
	}

	public static void main(String args[]) {
		TreeNode root = new TreeNode(10);
		root.left = new TreeNode(8);
		root.right = new TreeNode(2);
		root.left.left = new TreeNode(3);
		root.left.right = new TreeNode(5);
		root.right.left = new TreeNode(2);
		root.left.right.left = new TreeNode(5);

		ArrayList<Integer> path = new ArrayList<Integer>();
		ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();

		findPaths(root, 21, path, paths);
		System.out.println(paths);

		path.clear();
		paths.clear();
		findPaths(root, 23, path, paths);
		System.out.println(paths);

		path.clear();
		paths.clear();
		findPaths(root, 14, path, paths);
		System.out.println(paths);

		path.clear();
		paths.clear();
		findPaths(root, 5, path, paths);
		System.out.println(paths);
	}
}

以上代码中当输入的目标和为5时，仅仅返回两条路径。算法复杂度的分析和第一题一样，仍然是O(N*logN)。