队列 Queue 主要处理的问题是广度优先遍历（不论是针对树还是图，可以把树理解为图的特殊形式）。
例题：LeetCode 第 102 题：二叉树的层次遍历
传送门：102. 二叉树的层次遍历。
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树:[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7返回其层次遍历结果：
[ [3], [9,20], [15,7] ]
分析：非常标准的层序遍历的做法，使用队列作为辅助的数据结构。
Python 代码：
练习：LeetCode 第 107 题：二叉树的层次遍历 II
传送门：107. 二叉树的层次遍历 II。
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7返回其自底向上的层次遍历为：
[ [15,7], [9,20], [3] ]
Python 代码：
练习：LeetCode 第 103 题：二叉树的锯齿形层次遍历
传送门：103. 二叉树的锯齿形层次遍历。
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7返回锯齿形层次遍历如下：
[ [3], [20,9], [15,7] ]
Python 代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root is None:
return []
queue = [root]
res = []
turn_left = True
while queue:
cur_list = []
size = len(queue)
for _ in range(size):
top = queue.pop(0)
if turn_left:
cur_list.append(top.val)
else:
cur_list.insert(0, top.val)
if top.left:
queue.append(top.left)
if top.right:
queue.append(top.right)
res.append(cur_list)
turn_left = not turn_left
return res
练习：LeetCode 第 199 题： 二叉树的右视图
传送门：199. 二叉树的右视图。
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释: 1 <--- / \ 2 3 <--- \ \ 5 4 <---
分析：1、深度优先遍历；2、层序遍历（2种写法，本质上其实一样）。
Python 代码：
# 199. 二叉树的右视图
# 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
def dfs(node, res, depth):
if node is None:
return
if len(res) == depth:
res.append(node.val)
dfs(node.right, res, depth + 1)
dfs(node.left, res, depth + 1)
res = []
dfs(root, res, 0)
return res
（本节完）
