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

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); } }