一道二叉树打印题引发的deque介绍

首先题目是这样的：自上而下按照之字形打印二叉树，第一行按照从左到右的顺序打印，第二层按照从右到左。。。这道题我最初用的方法太蠢笨了，不好意思放上来，现在把评论区一位同志用回溯法的代码放出来。

from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res = []
        def dfs(node, level):
            if not node:
                return
            if level == len(res):
                res.append(deque([]))
            # append操作，偶数行从左到右；奇数行从右到左
            if level % 2 == 0:
                res[level].append(node.val)
            else:
                res[level].appendleft(node.val)
            dfs(node.left, level+1)
            dfs(node.right, level+1)


        dfs(root, 0)
        return res

他这个解法之所以巧妙是用到了python中的deque数据结构。

deque

使用list存储数据时，按索引访问元素很快，但是插入和删除元素就很慢了，因为list是线性存储，数据量大的时候，插入和删除效率很低。
deque是为了高效实现插入和删除操作的双向列表，适合用于队列和栈：

>>> from collections import deque
>>> q = deque(['a', 'b', 'c'])
>>> q.append('x')
>>> q.appendleft('y')
>>> q
deque(['y', 'a', 'b', 'c', 'x'])

——引自廖雪峰的官方网站
deque除了实现list的append()和pop()外，还支持appendleft()和popleft()，这样就可以非常高效地往头部添加或删除元素。