面试题中的二叉树根据和寻路径问题(2)

不过测试时发现这里存在重复递归，从而生成了冗余的路径。原因是我在进行对当前路径扩展的递归调用和生成新路径的递归调用使用的同一个函数接口。举个例子说明，假设输入的二叉树至少有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)。