6.3二叉树的层序遍历（LC102，LC107-M）

二叉树的层序遍历（LC102）：

算法（长度法）：

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

举个例子模拟一下：

对于空队列queue，创建一个level用于储藏每一层的值，创建应该result用于合并level。通过记录队列的长度，来判断level里面可以放多少个数:

1. push入6，记录此时的len(queue)==1
2. 将当前层元素弹出：leftpop 6\\level=[6]，len(queue)==0
3. push入6的左子树根节点4，此时的len(queue)==1
4. push入6的右子树根节点7，此时的len(queue)==2\\queue = [4,7]
5. 由于len(queue)==2，所以接下来只弹出两个元素：
   1. 首先popleft 4
   2. push入4的左子树根节点1\\queue=[7,1]
   3. push入4的右子树根节点3\\queue=[7,1,3]
   4. 接着popleft 7\\ len(queue)==0，level=[4,7]
   5. push入7的左子树根节点5\\queue=[1]
   6. push入7的右子树根节点8，此时的len(queue)==4\\queue=[1,3,5,8]
6. 由于len(queue)==4，所以接下来弹出4个元素：
7. level = [1,3,5,8]
8. 最后的result = [[6], [4,7], [1,3,5,8]]

正确代码：

from collections import deque
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if root == None:
            return res
        else:
            queue = deque([root])
            #只要queue非空，就要一直操作
            while queue:
                level = []
                #通过queue的长度控制弹出的个数
                for _ in range(len(queue)):
                    node = queue.popleft()
                    level.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                #把level的结果都放到res里面
                res.append(level)
            return res
 
 

时间空间复杂度：

时间复杂度为O(n)，其中n为二叉树中的节点个数，因为每个节点都会被访问一次。

空间复杂度为O(m)，其中m为二叉树中每一层的最大节点个数，即为队列`queue`的最大长度。

二叉树的层序遍历（LC107）：

算法：就是把LC102复现以后，把结果反转一下

代码：

from collections import deque
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
 
        res = []
        if root == None:
            return res
        else:
            queue = deque([root])
            #只要queue非空，就要一直操作
            while queue:
                level = []
                #通过queue的长度控制弹出的个数
                for _ in range(len(queue)):
                    node = queue.popleft()
                    level.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                #把level的结果都放到res里面
                res.append(level)
            res [:] = res [::-1]
            return res
 
 

时间空间复杂度：

这段代码的时间复杂度为O(n)，其中n为二叉树中的节点个数，因为每个节点都会被访问一次。空间复杂度为O(m)，其中m为二叉树中每一层的最大节点个数，即为双端队列`queue`的最大长度。