题解 | #二叉树中和为某一值的路径#

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

http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca

前序遍历二叉树,用list集合存储所经过的节点值
将当前节点值加入list,判断从根节点到当前节点和目标和的大小关系
1.大于或者此节点为null,返回。否则将当前节点加入list
2.等于,判断是否已经是叶子节点,是将当前集合加入结果集,
3.小于,继续去找当前节点的左右子节点进行判断
4.从list删除当前节点,返回,

public class Solution {
    public ArrayList<ArrayList<Integer>> res=new ArrayList();
    public ArrayList<Integer> list=new ArrayList();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
             dfs(root,target);
              return res;
    }
    public void dfs(TreeNode root,int target){
       //(1)
        if(root==null||target-root.val<0){
            return;
        }

         list.add(root.val);//加入当前节点值
        if(target-root.val==0&&root.left==null&&root.right==null){
            res.add(new ArrayList(list));  //(2)加入结果集
        }
         //递归(3)
        dfs(root.left,target-root.val);
        dfs(root.right,target-root.val);
         list.remove(list.size()-1);   //(4)回溯
    }
}
全部评论
楼主,target-root.val<0 这句代码不能加啊
点赞 回复 分享
发布于 2022-02-28 21:06
可以吧,加上就不用做后边的判断了,相当于剪枝。短路或运算符如果前边的值为true不会去再进行后边的的判断,不会有啥空指针异常的,还是你说的是其他原因?
点赞 回复 分享
发布于 2022-02-28 21:15
就是我这边的测试用例,节点值有负数的话就通过不了
点赞 回复 分享
发布于 2022-03-02 12:29

相关推荐

评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客企业服务