二叉树是面试里常考的一类数据结构，其中有一类寻找路径问题很有意思。目前见过两种类型题目，都是先给出一个和，然后要求打印出节点值之和与此相等的路径问题。
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 path, ArrayList> 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) 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 path = new ArrayList();
ArrayList> paths = new ArrayList>();
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.
这里仍然假设并不全为正数。不过这题有个地方说法可能不够严谨：对于任意的路径，是否允许两条自上而下的路径在最高处相交而和合成的一条路径的情况？例如，对于一个仅有3个节点的二叉树，根节点有左右两个孩子节点，那么从左孩子节点到右孩子节点的倒V字型路径到底算不算？显然，如果这样的路径也需要考虑的话，情况会更加复杂。不过我见过的题目里没有考虑到这种情况的。
这题仍然沿着上题的思路进行扩展即可，遇到任意一个节点：
1）延续当前路径和继续增加当前和；
2）从左右孩子节点开始一条新路径，并且将当前和清零。
@SuppressWarnings("unchecked")
public static void findPaths(TreeNode node, int sum, int curSum,
ArrayList path, ArrayList> 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) path.clone(), paths);
// start another new path from the left child node
findPaths(node.left, sum, 0, new ArrayList(), paths);
}
if (node.right != null) {
// continue the current path
findPaths(node.right, sum, curSum,
(ArrayList) path.clone(), paths);
// start another new path from the right child node
findPaths(node.right, sum, 0, new ArrayList(), paths);
}
}
不过测试时发现这里存在重复递归，从而生成了冗余的路径。原因是我在进行对当前路径扩展的递归调用和生成新路径的递归调用使用的同一个函数接口。举个例子说明，假设输入的二叉树至少有3层，在根节点搜索时，会产生两个搜索分支：
1.1）尝试让子节点延续以根节点为起点的路径；
1.2）尝试以子节点为起点的新路径。
而在子节点搜索时，对于分支1.1，会再产生两个搜索分支：
2.1）尝试让孙子节点延续以根节点为起点的路径；
2.2）尝试以孙子节点为起点的新路径。
对于分支1.2，也会产生两个搜索分支：
2.