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

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

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;
    }
}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务