LeetCode 102. 二叉树的层序遍历BFS

简介: LeetCode 102. 二叉树的层序遍历BFS

 LeetCode 102. 二叉树的层序遍历BFS

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

示例 1:

image.gif 编辑

输入:root = [3,9,20,null,null,15,7]

输出:[[3],[9,20],[15,7]]


示例 2:

输入:root = [1]

输出:[[1]]


示例 3:

输入:root = []

输出:[]


提示:

    • 树中节点数目在范围 [0, 2000]
    • -1000 <= Node.val <= 1000


    思路:利用队列 queue 先进先出的特性,按层次逐层遍历


    时间复杂度:O(N)

    空间复杂度:O(N)

    /*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/funclevelOrder(root*TreeNode) [][]int {
    res :=make([][]int, 0)
    queue :=make([]*TreeNode, 0)
    ifroot!=nil {
    queue=append(queue, root) // 首先,根节点入队    }
    forlen(queue) >0 {
    subRes :=make([]int, 0)
    length :=len(queue)    // 提前缓存上一轮queue大小,避免在内循环中append导致queue长度变化fori :=0; i<length; i++ {
    root :=queue[0]
    subRes=append(subRes, root.Val)
    queue=queue[1:]   // popifroot.Left!=nil {
    queue=append(queue, root.Left)
                }
    ifroot.Right!=nil {
    queue=append(queue, root.Right)
                }
            }
    res=append(res, subRes)
        }
    returnres}

    image.gif


    目录
    相关文章
    |
    3天前
    【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
    【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
    9 0
    |
    6天前
    |
    存储 Java
    JAVA数据结构刷题 -- 力扣二叉树
    JAVA数据结构刷题 -- 力扣二叉树
    12 0
    |
    7天前
    [LeetCode]—— 226——翻转二叉树
    [LeetCode]—— 226——翻转二叉树
    |
    7天前
    [LeetCode]——965——单值二叉树
    [LeetCode]——965——单值二叉树
    |
    7天前
    LeetCode——101——对称二叉树
    LeetCode——101——对称二叉树
    32 12
    |
    7天前
    |
    存储
    LeetCode———144—— 二叉树的前序遍历
    LeetCode———144—— 二叉树的前序遍历
    |
    7天前
    LeetCode——965. 单值二叉树
    LeetCode——965. 单值二叉树
    |
    3天前
    |
    索引
    【力扣刷题】两数求和、移动零、相交链表、反转链表
    【力扣刷题】两数求和、移动零、相交链表、反转链表
    11 2
    【力扣刷题】两数求和、移动零、相交链表、反转链表
    |
    2天前
    |
    算法
    "刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
    该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
    10 0
    |
    3天前
    |
    索引
    【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
    【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
    8 0