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

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

https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.stream.Collectors;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<>();
        LinkedList<Integer> queue = new LinkedList<>();
        int sumAll = 0;
        if (root != null) {
            addDatas(root, sum, results, queue, sumAll);
        }
        return results.size() > 0;
    }

    private void addDatas(TreeNode root, int expectNumber,
                          ArrayList<ArrayList<Integer>> results, LinkedList<Integer> queue, int sumAll) {
        if (root != null) {
            sumAll += root.val;
            queue.add(root.val);
            if (sumAll == expectNumber && root.left == null && root.right == null) {
                addResult(results, queue);
            } else {
                addDatas(root.left, expectNumber, results, queue, sumAll);
                addDatas(root.right, expectNumber, results, queue, sumAll);
            }
            queue.pollLast();
            sumAll -= root.val;
        }
    }


    private void addResult(ArrayList<ArrayList<Integer>> results,
                           LinkedList<Integer> queue) {
        // 循环队列中的元素
        ArrayList<Integer> result = (ArrayList)queue.stream().collect(
                                        Collectors.toList());
        results.add(result);
    }
}

解题思想:队列+递归+回朔

#算法##算法笔记#
全部评论

相关推荐

10-15 20:01
已编辑
上海大学 Java
钉钉什么垃圾公司,约面鸽人
光年在眼前:不是坏事,感觉钉钉挺逆天的,二面结束还给我留作业,让我使用钉钉和看最新的发布会,然后说感受,我是应该不会去,三面直接拒绝不面了
点赞 评论 收藏
分享
我的offer呢😡:这不才9月吗,26到明年毕业前能一直找啊,能拿下提前批,转正的,offer打牌的都是有两把刷子的,为什么非要跟他们比。如果别人是9本硕+金牌+好几段大厂实习呢?如果别人是双非通天代呢?如果别人是速通哥呢?,做好自己就行了,我们做不到他们一样提前杀死比赛,但晚点到终点也没啥关系吧
双非应该如何逆袭?
点赞 评论 收藏
分享
09-19 12:15
门头沟学院 Java
迷茫的大四🐶:这下是真的打牌了,我可以用感谢信和佬一起打牌吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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