题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
思路
简而言之，就是求所有从根结点到叶子节点的和等于某个数的列表，然后再用一个大的列表将他们都包括进去。
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> arrList = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> tempList =new ArrayList<Integer>();
int sum = 0;
findList(arrList,sum,tempList,root,target);
return arrList;
}
public void findList(ArrayList<ArrayList<Integer>> arrList,int sum,ArrayList<Integer> list, TreeNode root, int target){
if(root==null)
return;
list.add(root.val);
sum+=root.val;
if(sum==target && root.left==null && root.right==null)
arrList.add(new ArrayList<Integer> (list));
findList(arrList,sum,list,root.left,target);
findList(arrList,sum,list,root.right,target);
list.remove(list.size()-1);
}
}
精简版
public class Solution {
private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null) return listAll;
list.add(root.val);
target-=root.val;
if(target==0 && root.left==null && root.right==null)
listAll.add(new ArrayList<Integer>(list));
FindPath(root.left, target);
FindPath(root.right, target);
list.remove(list.size()-1);
return listAll;
}
}
注意一点：这里：
listAll.add(new ArrayList<Integer>(list));
为什么要new 一个ArrayList
listAll.add(list)了，这样的 话一直不通过。
查阅资料后发现：
ArrayList.add()，当添加的时候添加的并不是实体类，而是实体类的引用，相当于指针，存储的是也是存储的指针。所以我添加的都是b的引用，而这个引用并没有变化，所以最后ArrayList中的数据均指向最后一次封装的b。