二叉树中和为某一值的路径
二叉树中和为某一值的路径
http://www.nowcoder.com/questionTerminal/b736e784e3e34731af99065031301bca
不知道题目给的答案为什么都没有比较list长度,这属于错误吧,这是我调整的代码。
import java.util.ArrayList; //与传统的编码相同不过此处换成每个叶子结点的权值,和路径 public class Solution { public void preOrder(TreeNode T,int target,int sum,ArrayList<Integer> temp,ArrayList<ArrayList<Integer>> all){ if(T!=null){ temp.add(T.val); sum+=T.val; if(T.left==null && T.right==null){ //如果是叶子结点并且等于目标值,根据长度插入指定位置 if(sum==target){//按顺序插入就行,本身也是深度递增走的 int i; for(i=0;i<all.size();i++){//插入排序 if(temp.size()>all.get(i).size()) all.add(i,new ArrayList<Integer>(temp)); } //如果刚开始总list为空,或者list长度最低 if(i==(all.size()))all.add(new ArrayList<Integer>(temp)); } } preOrder(T.left,target,sum,temp,all); preOrder(T.right,target,sum,temp,all); temp.remove(temp.size()-1); } } public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { ArrayList<Integer> temp = new ArrayList<Integer>(); ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>(); preOrder(root,target,0,temp,all); return all; } }