LeetCode102题：二叉树的层序遍历（python3）

代码思路：使用队列先进先出的特性，queue[]不为空进入for循环，tmp存储每层的节点，将结果添加至res[]中。
python中使用collections中的双端队列deque()，其popleft()方法可达到O(1)时间复杂度。

class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return[]res,queue = [],collections.deque()queue.append(root)while queue:tmp = []for _ in range(len(queue)): #len(queue)的长度不为null就进入循环node = queue.popleft()tmp.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)  res.append(tmp)return res

列表的方法一般只支持尾部，例如pop、append，但是对于一些队列问题，需要在头部操作，则需要使用pop(0)、insert(0,x)等方法，不太方便，Python的collections包中的双端队列deque很好地解决了这个问题，增加了头部方法popleft、appendleft等。

from collections import dequealist=['a','b','c','d']
dq=deque(alist)
print(dq.pop())
print(dq.popleft())
print(dq)
dq.appendleft('e')
print(dq)

d
a
deque(['b', 'c'])
deque(['e', 'b', 'c'])