专栏首页IT那个小笔记102 二叉树的层序遍历

102 二叉树的层序遍历

01

题目信息

题目地址: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

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

示例:

二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层序遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

02

解法一:广度优先遍历

没想到这题居然是中等,来人啊!

言归正传,题目让你层序遍历也就是广度遍历然后放到容器里。就是纯遍历一次没有别的操作了

public List<List<Integer>> levelOrder(TreeNode root) {
    //定义结果集
    List<List<Integer>> result = new ArrayList<>();
    //根节点为空
    if(root = null) return result;
    //实现队列(也可以用别的LinkedList快一点)
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while(!queue.isEmpty()){
        //每一层的遍历
        List<Integer> level = new ArrayList<Integer>();
        int size = queue.size();
        for(int i = 0; i < size; i++){
            TreeNode node = queue.poll();
            level.add(node);
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

遍历整个树时间复杂度O(n),队列小于n空间复杂度为O(n)

03

解法二:深度优先遍历

这里我们折腾一下,这题广度就是题目它的意思来的。但偏偏就要用深度写下

不同的是广度每次内层循环就完成一层节点的遍历,外层去添加这一层的List,深度的话遍历第一个是第一层的第二个就是第二层了第三个就是第三层的第一个了,因此需要先记下层级

public List<List<Integer>> levelOrder(TreeNode root) {
    //结果集
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(root == null) return result;
    dfs(1,root,result);
    return result;
} 
public void dfs(int level, TreeNode root, List<List<Integer>> result) {
    //容器大小小于层级则添加一个新层级
    if(result.size()<level) {
        result.add(new ArrayList<Integer>());
    }
    //往对应的层级List添加值
    result.get(level - 1).add(root.val);
    //往下面走,层级+1
    if(root.left!=null) {
        dfs(level+1, root.left, result);
    }
    if(root.right!=null) {
        dfs(level+1, root.right, result);
    }
}

04

总结

还是与之前一样,用来熟悉树的遍历,基本上一个题两大种遍历方式都是可以完成,只不过是适用性不一样。总之多思考多熟练树遍历的操作过程

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 102. 二叉树的层序遍历

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

    CaesarChang张旭
  • LeetCode 102. 二叉树的层序遍历

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

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

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

    程序IT圈
  • Leetcode|二叉树的遍历方式|102. 二叉树的层序遍历

    这里再积累一个二维vector的插入写法,即利用vec2d.back()方法调用二维向量中的一维向量

    SL_World
  • LeetCode 102. 二叉树的层序遍历 Binary Tree Level Order Traversal (广度优先搜索(BFS))

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

    一个会写诗的程序员
  • 【Leetcode】102. 二叉树的层次遍历

    我们数据结构的书上教的层序遍历,就是利用一个队列,不断的把左子树和右子树入队。但是这个题目还要要求按照层输出。所以关键的问题是: 如何确定是在同一层的。 我们很...

    Leetcode名企之路
  • LeetCode | 102.二叉树的层次遍历

    上面的题就是 二叉树的层次遍历 题目的截图,同时 LeetCode 会根据选择的语言给出一个类的定义或者函数的定义,然后在其中实现 二叉树的层次遍历 的解题过程...

    码农UP2U
  • 【LeetCode】102. 二叉树的层次遍历

    3 / \ 9 20 / \ 15 7 返回其层次遍历结果:

    韩旭051
  • LeetCode 102. 二叉树的层次遍历(BFS)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-level-order-tra...

    Michael阿明
  • LeetCode 102.二叉树的层次遍历 - JavaScript

    题目描述:给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

    心谭博客
  • 二叉树层序遍历

    大忽悠爱学习
  • 二叉树的层序遍历

    大忽悠爱学习
  • 每天一道leetcode-102二叉树的层次遍历

    乔戈里
  • 二叉树:层序遍历登场!

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

    代码随想录
  • LeetCode144.二叉树的前序遍历&94.二叉树的中序遍历&145.二叉树的后序遍历

     后序遍历的非递归代码得说一下,首先后序遍历得顺序是左右中,我们知道先序遍历的压栈顺序是先压右再压左,这样出来的顺序就是中左右,如果把先序遍历的压栈顺序稍微变一...

    mathor
  • 二叉树层次遍历

    二叉树层次遍历,又称为宽度优先搜索,按树的层次依次访问树的结点。层次遍历使用队列对遍历节点进行 存储,先进入队列的结点, 优先遍历拓展其左孩子与 右孩子。

    小飞侠xp
  • 二叉树的层次遍历

    二叉树的层次遍历 基本思想 借助队列来实现 首先初始化队列.然后将根结点压入队列 然后出队,输出出队元素的值, 如果存在左孩子.则左孩子入队 如果存在右孩子,则...

    李家酒馆酒保
  • 二叉树的分层遍历

    给定一棵二叉树,要求从上到下从左到右分层输出该二叉树的节点值。 ? bitree.png 一、递归法 二叉树本身就带有递归属性,通常我们可以用递归方法解决。假设...

    海天一树
  • LC94–二叉树的中序遍历—144. 二叉树的前序遍历

    LC94--二叉树的中序遍历---144. 二叉树的前序遍历 ...

    Java架构师必看

扫码关注云+社区

领取腾讯云代金券