​LeetCode刷题实战102:二叉树的层序遍历

程序IT圈

共 2308字,需浏览 5分钟

 ·

2020-11-23 21:27

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 二叉树的层序遍历,我们先来看题面:

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

题意


给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。

样例

解题

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/tao-mo-ban-bfs-he-dfs-du-ke-yi-jie-jue-by-fuxuemin/


本题是让我们把二叉树的每一层节点放入到同一个列表中,最后返回各层的列表组成的总的列表。
可以使用 BFS 和 DFS 解决。
左边是BFS,按照层进行搜索;图右边是DFS,先一路走到底,然后再回头搜索。



方法一:BFS


BFS使用队列,把每个还没有搜索到的点依次放入队列,然后再弹出队列的头部元素当做当前遍历点。


class Solution {
    public List<List> levelOrder(TreeNode root) {
        List<List> res = new ArrayList<>();
        Queue q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List level = new LinkedList<>();
            for (int i = 0; i < size; ++i) {
                TreeNode cur = q.peek();
                q.poll();
                if (cur == null) {
                    continue;
                }
                level.add(cur.val);
                q.offer(cur.left);
                q.offer(cur.right);
            }
            if (!level.isEmpty()) {
                res.add(level);
            }
        }
        return res;
    }
}


方法二:DFS

本题使用 DFS 同样能做。由于题目要求每一层的节点都是从左到右遍历,因此递归时也要先递归左子树、再递归右子树。

DFS 做本题的主要问题是:DFS 不是按照层次遍历的。为了让递归的过程中同一层的节点放到同一个列表中,在递归时要记录每个节点的深度 level。递归到新节点要把该节点放入 level 对应列表的末尾。

当遍历到一个新的深度 level,而最终结果 res 中还没有创建 level 对应的列表时,应该在 res 中新建一个列表用来保存该 level 的所有节点。


class Solution {
    public List<List> levelOrder(TreeNode root) {
        List<List> res = new ArrayList<>();
        if(root != null){
            dfs(res, root, 0);
        }
        return res;
    }
    
    private void dfs(List<List> res, TreeNode node, int level){
        if(res.size() - 1 < level){
            res.add(new ArrayList());
        }
        res.get(level).add(node.val);
        if(node.left!=null){
            dfs(res, node.left, level + 1);
        }
        if(node.right!=null){
            dfs(res, node.right, level + 1);
        }
    }
}



好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。


上期推文:

LeetCode1-100题汇总,希望对你有点帮助!
LeetCode刷题实战101:对称二叉树

浏览 27
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报