剑指Offer 25 *二叉树中和为某一值的路径

题目描述

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

思路

这道题绝对就是递归了，但是你会发现一个问题，怎么做到已经找到一条路径然后还要继续找

代码

ArrayList<ArrayList<Integer>> arrayLists= new ArrayList<>();
 ArrayList<Integer> list = new ArrayList<>();
 public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
     if ( root ==null)
         return arrayLists;
     target -=root.val;
     list.add(root.val);
     if (target==0&&root.left==null&&root.right==null)
     {
         arrayLists.add(new ArrayList<>(list));
     }
     FindPath(root.left,target);
     FindPath(root.right,target);
     list.remove(list.size()-1);
     return  arrayLists;
 }

首先我们拆开看,下面其实是一个先序遍历，每一项都可以到达；

ArrayList<ArrayList<Integer>> arrayLists= new ArrayList<>();
 ArrayList<Integer> list = new ArrayList<>();
 public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
     list.add(root.val);
     FindPath(root.left,target);
     FindPath(root.right,target);
 }

list用于记录当前路径，如果遍历过左右，说明要遍历其他的了，所以可以

1	list.remove(list.size()-1); //删除路径中的当前位置，因为它的两条子路都不能走

接下来就是添加各种条件了；
不能为空，必须是叶节点；

if ( root ==null)
          return arrayLists;
      if (target==0&&root.left==null&&root.right==null)
      {
          arrayLists.add(new ArrayList<>(list));
      }

收获

递归真的好难写，这道题可以偶尔拿出来练练手；

2017-03-26