102. 二叉树的层序遍历

已解答

中等

相关标签

相关企业

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

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution(object):

    def levelOrder(self, root):

        """

        :type root: Optional[TreeNode]

        :rtype: List[List[int]]

        """

        # 广度优先搜索

        if root ==None:

            return []

        queue = []

        final=[]

        queue.append(root)

        while queue!=[]:

            left = len(queue)

            # final.append(queue[0])

            queue_next=[]

            for i in range(left):

                if queue[i].left:

                    queue_next.append(queue[i].left)

                if queue[i].right:

                    queue_next.append(queue[i].right)

           

            final.append([x.val for x in queue])

           

            queue = queue_next

            queue_next=[]

        return final

 

           

       

直接使用广度优先搜索去做，但是需要注意的是，我们需要额外去维护一个每一个层的lsit