Leetcode102. 二叉树的层序遍历 Binary Tree Level Order Traversal - Python 以递归/迭代算法实现

# 递归法
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if not root: return []

        def traversal(root: TreeNode, depth = 0):
            if len(result) == depth: result.append([])  #当遍历到新的下一层后，新建一层[]
            result[depth].append(root.val) #遇到根节点就将其加入相应层中
            if root.left: traversal(root.left, depth + 1)
            if root.right: traversal(root.right, depth + 1) 
            #实际上该递归的结束条件为 root.left == None 和 root.right == None
        traversal(root, 0)
        return result

递归思路：

找准递归的三要素：

1.调用函数参数：root，depth-当前深度

2.函数体具体操作：当遇到新层，则添加[]；遇到父节点就将root.val输出；然后分别将左孩子、右孩子依次用遍历父节点一样的方式（递归的方式）遍历孩子节点。

3.递归终止条件： #实际上该递归的结束条件为 root.left == None 和 root.right == None

需理解：

递归算法层序遍历二叉树，不是像迭代一样，依次遍历每一层的节点。而是深度优先，先依次遍历并到达最深的孩子节点，然后再往回走。如此，可能深层已经被遍历完毕，而浅层却还没有被遍历完毕。

class Solution:
    """二叉树层序遍历迭代解法"""

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        results = []
        if not root: return results

        from collections import deque
        queue = deque([root])


        while queue:
            child_size = len(queue) #每一层待遍历的节点个数
            result = []    
            for _ in range(child_size):
                cur = queue.popleft()
                result.append(cur.val)

                #将左右孩子依次加入下一层待遍历节点队列中（dequeue）
                if cur.left: queue.append(cur.left)    
                if cur.right: queue.append(cur.right)
            results.append(result)
        return results

迭代法思路：

调用deque双向队列，double-ended queue；

将每一层的节点依次从右侧(默认)加入dequeue；

依次遍历每一层的节点值，对每一个节点，遇到左右孩子非空的，加入到dequeue中；

每一层的节点遍历结果记录在result中，每一层遍历结束后，将结果加入results。