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

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

public static void findPaths(TreeNode node, int sum,
ArrayList path, ArrayList> 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(), paths);
findPaths(node.right, sum, new ArrayList(), paths);
}

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

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

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

continueCurPath(node.left, sum, curSum,
(ArrayList) path.clone(), paths);
continueCurPath(node.right, sum, curSum,
(ArrayList) 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 path = new ArrayList();
ArrayList> paths = new ArrayList>();

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)。