2022-02-20二叉树层序遍历

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

递归的解法

# 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: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        self.helper(root, 0, result)
        return result

    def helper(self, root, level, result):
        if len(result) == level:
            result.append([])
        result[level].append(root.val)
        if root.left:
            self.helper(root.left, level+1, result)
        if root.right:
            self.helper(root.right, level+1, result)
        
       

使用dummy标记进行迭代

# 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: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        dummy = TreeNode()
        p = root
        queue = [root, dummy]
        level = []
        while queue:
            # print("queue,p", [e.val for e in queue],p.val)
            p = queue.pop(0)
            if p != dummy:
                level.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right)
            else:
                result.append(list(level))
                level = []
                # 若队列中已无数据，则不再添加标记节点
                if queue:
                    queue.append(dummy)
        return result
          

迭代：每次直接遍历一层的数据

我们可以用一种巧妙的方法修改广度优先搜索：
首先根元素入队
当队列不为空的时候:
求当前队列的长度Si
依次从队列中取 Si个元素进行拓展，然后进入下一次迭代

它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取 Si个元素。

# 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: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        p = root
        queue = [root]
        while queue:
            levelQueue = []
            level = len(queue)
            # print("queue, level", [e.val for e in queue], level)
            for i in range(level):
                p = queue.pop(0)
                levelQueue.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right)
            result.append(list(levelQueue))
        return result
           

如果是要求蛇形打印，也可以通过调整左右子树的先后顺序做出改变