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

题目

  • 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)

思路


代码

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    //存储路径的容器
    ArrayList<ArrayList<Integer>> resultlist = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        //每个路径----用来存储节点的容器
        ArrayList<Integer> path = new ArrayList<Integer>();
        if(root==null)
            return resultlist;
        //路径每个节点数值之和
        int currentSum =0;
        FindPath(root,target,currentSum,path);
        return resultlist;
    }
    public void FindPath(TreeNode root,int target,int currentSum,ArrayList<Integer> path){
        if(root==null)
            return;
        //首先判断第一个根节点的值与target是否相同
        currentSum+=root.val;
        //将根节点元素添加到路径中
        path.add(root.val);
        //如果根节点没有左右节点,那么则直接判断是否值为target,如果相同则添加路径path到resultlist中
        if(root.left==null && root.right ==null){
            if(currentSum==target){
                resultlist.add(new ArrayList<Integer>(path));
                //将路径的叶节点删除,再继续寻找别的情况target
                path.remove(path.size()-1);
                return;
            }
        }
        //如果根节点还有左右子节点,那么直接递归左右子树的情况
        FindPath(root.left,target,currentSum,path);
        FindPath(root.right,target,currentSum,path);
        //这里左右子树都找完了,回到了找完的左右子树的父节点
       //由于父节点的左右子树找完了,所以父节点这里也没有用了,把父节点删除
        path.remove(path.size()-1);
    }
}
全部评论

相关推荐

05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
点赞 评论 收藏
分享
05-20 13:59
门头沟学院 Java
米黑子米黑子:你这个成绩不争取下保研?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务