专栏首页木又AI帮打卡群2刷题总结1010——二叉树的层序遍历

打卡群2刷题总结1010——二叉树的层序遍历


leetcode第102题:二叉树的层序遍历

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]
]

【思路】

使用队列,只要队列不为空,则遍历队列元素,并将孩子节点加入新队列中,遍历结束后,将新队列复制给原始的队列。

【代码】

python版本

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        queue = [root]
        res = []
        # 只要不为空,就得继续遍历
        while len(queue) > 0:
            tmp = []
            res_tmp = []
            # 遍历所有元素
            while len(queue) > 0:
                node = queue.pop(0)
                if not node:
                    continue
                res_tmp.append(node.val)
                tmp.append(node.left)
                tmp.append(node.right)

            if len(res_tmp) > 0:
                queue = tmp
                res.append(res_tmp)
        return res

【相似题目】

103. 二叉树的锯齿形层次遍历

解题思路:层次遍历,对偶数层的结果逆序。

107. 二叉树的层次遍历 II

解题思路:层次遍历+结果逆序。

429. N叉树的层序遍历

解题思路:层次遍历。

637. 二叉树的层平均值

解题思路:层次遍历+对每一层的所有元素取平均值。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

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

原始发表时间:2020-10-11

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0808——二叉树的层序遍历

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 打卡群2刷题总结1009——二叉树的中序遍历

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

    木又AI帮
  • 打卡群刷题总结0804——二叉树的中序遍历

    非递归解法,需要使用栈结构,同时使用一个visit数组标识该节点是否访问过其孩子节点。得到visit栈顶元素,判断是否访问过;如果访问过,则val加入到结果中;...

    木又AI帮
  • 打卡群刷题总结0809——二叉树的锯齿形层次遍历

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

    木又AI帮
  • 打卡群2刷题总结1011——从前序与中序遍历序列构造二叉树

    https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder...

    木又AI帮
  • 打卡群刷题总结0811——从中序与后序遍历序列构造二叉树

    链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-posto...

    木又AI帮
  • 打卡群刷题总结0810——从前序与中序遍历序列构造二叉树

    链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inor...

    木又AI帮
  • 打卡群2刷题总结1012——二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    木又AI帮
  • 打卡群2刷题总结1013——不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    木又AI帮
  • LeetCode刷题DAY 15:二叉树的层序遍历

    广度优先算法(Breadth-First-Search, BFS)指先访问当前节点的所有邻接节点,然后再不断扩张,是一种依靠队列实现的算法(先进先出,把每个还没...

    三猫
  • 打卡群刷题总结0807——验证二叉搜索树

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • ​LeetCode刷题实战102:二叉树的层序遍历

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

    程序IT圈
  • LeetCode刷题DAY 16:二叉树的层序遍历II

    根据层序遍历,自底向上返回一棵二叉树的节点值(从下至上逐层从左至右访问)。比如输入如下树:

    三猫
  • 打卡群刷题总结0805——不同的二叉搜索树

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 打卡群刷题总结0813——二叉树展开为链表

    链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

    木又AI帮
  • 打卡群刷题总结0814——二叉树展开为链表

    链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

    木又AI帮
  • 本周小结!(二叉树)

    发现大家周末的时候貌似都不在学习状态,周末的文章浏览量和打卡情况照工作日差很多呀,可能是本周日是工作日了,周六得好好放松放松,哈哈,理解理解,但我还不能不更啊,...

    代码随想录
  • 二叉树:层序遍历登场!

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

    代码随想录
  • 二叉树:总结篇!(需要掌握的二叉树技能都在这里了)

    不知不觉二叉树已经和我们度过了「三十三天」,代码随想录里已经发了「三十三篇二叉树的文章」,详细讲解了「30+二叉树经典题目」,一直坚持下来的录友们一定会二叉树有...

    代码随想录

扫码关注云+社区

领取腾讯云代金券