【Leetcode】剑指Offer 32-III： 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其层次遍历结果： [ [3], [20,9], [15,7] ] 提示： 节点总数 List[List[int]]: if root == None: return [] queue = [root] res = [] flag = 0 while queue: length = len(queue) temp = [] if flag & 1: for i in range(length - 1, -1, -1): temp.append(queue[i].val) if queue[i].right: queue.append(queue[i].right) if queue[i].left: queue.append(queue[i].left) queue.remove(queue[i]) queue = queue[::-1] else: for i in range(length): temp.append(queue[0].val) if queue[0].left: queue.append(queue[0].left) if queue[0].right: queue.append(queue[0].right) queue.remove(queue[0]) res.append(temp) flag += 1 return res

今天的题目确实应该能算上是中等题目了，需要一定的思考，不过如果直接掉包用reverse的话难度也没有太大。只是反向入队列的时候要注意不是先left再right。

妙解

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

作者：jyd
链接：https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er--3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

说实话这个双端队列其实挺蠢的。。但是最开始确实没想出来，笔者一直在思考怎么改变queue的入队列顺序，而官方解法中是temp当成了一个双端队列，通过头尾不同方式添加元素再在最后转回list来实现需求。