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

题目介绍

描述：

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \\
  9  20
    /  \\
   15   7
返回其层次遍历结果：

[
  [3],
  [20,9],
  [15,7]
]

提示：

节点总数 <= 1000

解题思路：

递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果。

写树相关的算法，简单说就是，先搞清楚当前 root 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

二叉树题目的一个难点在于如何通过题目的要求思考出每一个节点需要做什么

二叉树解题策略

一递归二队列 + 迭代（层次遍历）三栈 + 迭代（非递归遍历）四其它

三种基本的遍历方式，都可以用递归来实现。写递归算法的时候，需要注意递归退出条件以及递归操作的表达。

自己的解法实现

def levelOrder4(self, root):
        if not root: return []
        res, stack = [], [root]
        while stack:
            tmp = []
            for _ in range(len(stack)):
                node = stack.pop(0)
                tmp.append(node.val)
                if node.left: stack.append(node.left)
                if node.right: stack.append(node.right)
            res.append(tmp[::-1] if len(res) % 2 else tmp)
        return res

网上比较优秀的解法

解法一

方法一：层序遍历 + 双端队列利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列） tmp ，并规定：奇数层则添加至 tmp 尾部，偶数层则添加至 tmp 头部。

算法流程：

特例处理：当树的根节点为空，则直接返回空列表 [] ；
初始化：打印结果空列表 res ，包含根节点的双端队列 deque ；
BFS 循环：当 deque 为空时跳出； 4新建列表 tmp ，用于临时存储当前层打印结果；当前层打印循环：循环次数为当前层节点数（即 deque 长度）；出队：队首元素出队，记为 node；打印：若为奇数层，将 node.val 添加至 tmp 尾部；否则，添加至 tmp 头部；添加子节点：若 node 的左（右）子节点不为空，则加入 deque ；将当前层结果 tmp 转化为 list 并添加入 res ；返回值：返回打印结果列表 res 即可；

def levelOrder(self, root):
        from collections import deque
        if not root: return []
        res, queue = [], deque([root])
        while queue:
            tmp = deque()
            for _ in range(len(queue)):
                node = queue.popleft()
                if len(res) % 2:
                    tmp.appendleft(node.val)  # 偶数层 -> 队列头部
                else:
                    tmp.append(node.val)  # 奇数层 -> 队列尾部
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(list(tmp))
        return res

解法二

方法二：层序遍历 + 双端队列（奇偶层逻辑分离）方法一代码简短、容易实现；但需要判断每个节点的所在层奇偶性，即冗余了 NN 次判断。通过将奇偶层逻辑拆分，可以消除冗余的判断。算法流程：与方法一对比，仅 BFS 循环不同。

BFS 循环：循环打印奇 / 偶数层，当 deque 为空时跳出；打印奇数层：从左向右打印，先左后右加入下层节点；若 deque 为空，说明向下无偶数层，则跳出；打印偶数层：从右向左打印，先右后左加入下层节点；

def levelOrder2(self, root):
        from collections import deque
        if not root: return []
        res, queue = [], deque()
        queue.append(root)
        while queue:
            tmp = []
            # 打印奇数层
            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

解法三

方法三：层序遍历 + 倒序此方法的优点是只用列表即可，无需其他数据结构。偶数层倒序：若 res 的长度为奇数，说明当前是偶数层，则对 tmp 执行倒序操作。

def levelOrder3(self, root):
        from collections import deque
        res, queue = [], deque([root])

        while queue:
            tmp = []
            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[::-1] if len(res)%2 else tmp)
        return res