二叉树中和为某一值的路径

二叉树中和为某一值的路径

• ps：这道题的数据没有去验证是不是长度最长的靠左，所以我自己的代码也没有去写长度最长在左的验证
• Tips：
  1. 寻找路径，本能反应是递归
  2. 根据定义，因为要向下找到叶子节点，所以本能反应是深搜
  3. 递归分析
     1. 如果是空节点，直接返回null
     2. 如果不是空节点，且root.val != target,那么就是左子树深搜 + 右子树深搜
     3. 如果不是空节点，且且root.val == target && &&root.left==null&&root.right==null，说明找到了叶子节点，且满足条件，那么就返回节点值，终止循环。
  4. 特例分析，如果是{}，0的情况，需要特殊处理

代码如下：

ArrayList<ArrayList<Integer>> res = new ArrayList<>() ;

        ArrayList<ArrayList<Integer>> l_res = new ArrayList<>() ; //左子树深搜结果
        ArrayList<ArrayList<Integer>> r_res = new ArrayList<>() ; // 右子树深搜结果


        if (root!=null) {
            if (target == root.val&&root.left==null&&root.right==null) { //找到路径，满足条件
                ArrayList<Integer> array = new ArrayList<>() ;
                array.add(target) ;
                res.add(array) ;
                return res;
            } else { // 当前不满足条件
                //左子树深搜
                l_res = FindPath(root.left,target-root.val) ;
                //右子树深搜
                r_res = FindPath(root.right,target-root.val) ;

                if (l_res!=null || r_res!=null){ //看看深搜是不是找到了我们需要的结果

                    if (l_res!=null){ // 左子树满足条件

                        for (int i=0;i<l_res.size();i++){ //遍历返回的结果
                            ArrayList<Integer> arrayList = new ArrayList<>() ;
                            arrayList.add(root.val) ; // 当前路径 = 当前节点的值 + 递归下面子树的结果
                            for (int j=0;j<l_res.get(i).size();j++){
                                arrayList.add(l_res.get(i).get(j)) ; 
                            }
                            res.add(arrayList) ;
                        }
                    }

                    if (r_res!=null){ // 右子树满足条件，下面的分析和左子树一样
                        for (int i=0;i<r_res.size();i++){ 
                            ArrayList<Integer> arrayList = new ArrayList<>() ;
                            arrayList.add(root.val) ;
                            for (int j=0;j<r_res.get(i).size();j++){
                                arrayList.add(r_res.get(i).get(j)) ;
                            }
                            res.add(arrayList) ;
                        }
                    }


                }

                return res ;


            }
        }else if (root==null&&target==0) { // 特殊情况考虑
            res.clear();
            return res ;
        }else { // root==null 的情况 => 可能是直接就是空节点  =>也可能是遍历到了叶子节点也没找到结果
            return null ;
        }