剑指OfferJZ24：二叉树中和为某一值的路径-java版

JZ24:

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

深搜（dfs） 深搜，看名字就知道到是优先往深处找，不撞南墙终不悔。深搜，像是一个人走迷宫，遇见岔路不知道怎么走，就瞎选一个（程序中一搬从头遍历），走到底，不对，回到岔路口，选另一条路，接着走。

深搜的实现一般用栈或递归，不断深入。

宽搜（bfs） 宽搜全名宽度搜索，就是放宽了搜，就像是雷达那样，中间一个点不断放出电磁波，一圈一圈往外扩散，很容易就能发现目标，而且发现了必然就是最近的（最优解）。

宽搜的实现一般使用队列，不断扩散。

例：从树的根结点开始往下一直到叶子结点为一条路径，若这条路径结点值的等于你输入的整数，打印出该路径 根据题意可知使用深搜dfs方法， 如图，从根节点1开始一直往下搜索，经过2一直到叶子节点4结束，此时计算（权值和）1+2+4=7不等于8，便返回（回溯）到上一个节点2，同时去掉4节点的数值；在节点2处继续往深处搜索一直到叶子结点5结束，此时计算1+2+5=8，满足，打印出该路径；

public class jz24 {

   private ArrayList ans;

   /**
    *
    * @param root 根节点
    * @param target 输入的整数
    * @return
    */
   public ArrayList FindPath(TreeNode root, int target) {
       ans=new ArrayList();
       ArrayList list = new ArrayList();
       solve(root,target,0,list);
       return ans;
   }

   /**
    * @param node 二叉树节点
    * @param target 输入的整数
    * @param sum 当前路径的权值和
    * @param list 保存当前路径
    */

   private void solve(TreeNode node, int target, int sum, ArrayList list) {

       if(node!=null){
           sum+=node.val;
           list.add(node.val);
           if(node.left==null && node.right==null) {//当前节点是叶子结点
               if (sum == target) {//找到一条路径
                   ArrayList res = new ArrayList(list);
                   ans.add(res);
               }
           }
           else{
               solve(node.left,target,sum,list);//递归左子树
               solve(node.right,target,sum,list);//递归右子树
           }
           //消除掉当前节点对查找路径的影响（从当前节点回溯到上一层）
           list.remove(list.size()-1);
       }
   }
}