剑指 Offer 32 - III. 从上到下打印二叉树 III

题目描述

• 方法一
• 方法二：层序遍历 + 双端队列（奇偶层逻辑分离）

依旧按每层从左到右的顺序保存和输出，另设置layer变量指示当前层数，若为偶数层则顺序，奇数层则逆序

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res, queue = [], collections.deque()
        queue.append(root)
        layer = 0   # 当前的层数
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                tmp.append(node.val)
            if layer % 2 == 0:
                res.append(tmp)
            else:
                res.append(tmp[::-1])
            layer += 1
        return res

参考解法
方法一代码简短、容易实现；但需要判断每个节点的所在层奇偶性，即冗余了 N N N 次判断。
通过将奇偶层逻辑拆分，可以消除冗余的判断。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            tmp = []
            # 偶数层（从0开始）
            for _ in range(len(queue)):
                # 从左边出队列
                node = queue.popleft()
                tmp.append(node.val)
                # 从左往右入队列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(tmp)
            # 进行完一层后先做判断，如果为空则结束
            if not queue:
                break
            tmp = []
            # 奇数层
            for _ in range(len(queue)):
                # 从右边出队列
                node = queue.pop()
                tmp.append(node.val)
                # 从右往左从左端入队列,
                if node.right:
                    queue.appendleft(node.right)
                if node.left:
                    queue.appendleft(node.left)
            res.append(tmp)
        return res