二叉树中和为某一值的路径
二叉树中和为某一值的路径
http://www.nowcoder.com/questionTerminal/b736e784e3e34731af99065031301bca
二叉树中和为某一值的路径
- ps:这道题的数据没有去验证是不是长度最长的靠左,所以我自己的代码也没有去写长度最长在左的验证
- Tips:
- 寻找路径,本能反应是递归
- 根据定义,因为要向下找到叶子节点,所以本能反应是深搜
- 递归分析
- 如果是空节点,直接返回null
- 如果不是空节点,且root.val != target,那么就是左子树深搜 + 右子树深搜
- 如果不是空节点,且且root.val == target && &&root.left==null&&root.right==null,说明找到了叶子节点,且满足条件,那么就返回节点值,终止循环。
- 特例分析,如果是{},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 ; }