102. 二叉树的层序遍历

题目描述

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

思路

层序遍历用广度优先搜索更容易实现，可以使用一个队列进行先进先出的操作。因为我们要逐层打印，因此需要一个标志去代表当前这一层已经打印完了。那么怎样知道本层已经遍历完了呢？可以举个简单的例子。对于下面的二叉树：

   1
 2   3
4 5 6 7

最开始的队列是 [1]，那么我们只需要循环一次就可以了，接下来添加 [2, 3]，因此再村换两次。我们在循环之前通过 len(deque) 即可判断本次循环的长度。

最终代码：

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ans, dq = [], deque([root])
        while len(dq) > 0:
            l = len(dq)
            line = []
            for _ in range(l):
                top = dq.popleft()
                line.append(top.val)
                if top.left:
                    dq.append(top.left)
                if top.right:
                    dq.append(top.right)
            ans.append(line)
        return ans

想得太多