二叉树的层序遍历

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

 

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

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

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

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

解题思路,比较标准的广度优先遍历方法,先创建一个遍历栈,然后依次将每层的结点放入待遍历栈中,每次放入下一结点前,将该结点的值放入ans结果列表中即可。

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack = [root]
        ans = []
        while stack:
            next_stack = list()
            layer = list()
            for node in stack:
                layer.append(node.val)
                if node.left:
                    next_stack.append(node.left)
                if node.right:
                    next_stack.append(node.right)

            ans.append(layer)
            stack = next_stack
        return ans
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00