二叉树是面试里常考的一类数据结构，其中有一类寻找路径问题很有意思。目前见过两种类型题目，都是先给出一个和，然后要求打印出节点值之和与此相等的路径问题。
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.
这里仍然假设并不全为正数。不过这题有个地方说法可能不够严谨：对于任意的路径，是否允许两条自上而下的路径在最高处相交而和合成的一条路径的情况？例如，对于一个仅有3个节点的二叉树，根节点有左右两个孩子节点，那么从左孩子节点到右孩子节点的倒V字型路径到底算不算？显然，如果这样的路径也需要考虑的话，情况会更加复杂。不过我见过的题目里没有考虑到这种情况的。
这题仍然沿着上题的思路进行扩展即可，遇到任意一个节点：
1）延续当前路径和继续增加当前和；
2）从左右孩子节点开始一条新路径，并且将当前和清零。
@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);
}
}