隊列 Queue 主要處理的問題是廣度優(yōu)先遍歷（不論是針對樹還是圖抡蛙，可以把樹理解為圖的特殊形式）护昧。
例題：LeetCode 第 102 題：二叉樹的層次遍歷
傳送門：102. 二叉樹的層次遍歷。
給定一個二叉樹粗截，返回其按層次遍歷的節(jié)點值惋耙。 （即逐層地，從左到右訪問所有節(jié)點）熊昌。
例如:
給定二叉樹:[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7返回其層次遍歷結(jié)果：
[ [3], [9,20], [15,7] ]
分析：非常標(biāo)準(zhǔn)的層序遍歷的做法绽榛，使用隊列作為輔助的數(shù)據(jù)結(jié)構(gòu)。
Python 代碼：
練習(xí)：LeetCode 第 107 題：二叉樹的層次遍歷 II
傳送門：107. 二叉樹的層次遍歷 II婿屹。
給定一個二叉樹灭美，返回其節(jié)點值自底向上的層次遍歷。 （即按從葉子節(jié)點所在層到根節(jié)點所在的層昂利，逐層從左向右遍歷）
例如：
給定二叉樹[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7返回其自底向上的層次遍歷為：
[ [15,7], [9,20], [3] ]
Python 代碼：
練習(xí)：LeetCode 第 103 題：二叉樹的鋸齒形層次遍歷
傳送門：103. 二叉樹的鋸齒形層次遍歷届腐。
給定一個二叉樹，返回其節(jié)點值的鋸齒形層次遍歷页眯。（即先從左往右梯捕，再從右往左進(jìn)行下一層遍歷，以此類推窝撵，層與層之間交替進(jìn)行）傀顾。
例如：
給定二叉樹[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
練習(xí)：LeetCode 第 199 題： 二叉樹的右視圖
傳送門：199. 二叉樹的右視圖。
給定一棵二叉樹碌奉，想象自己站在它的右側(cè)短曾，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點值赐劣。
示例:
輸入: [1,2,3,null,5,null,4] 輸出: [1, 3, 4] 解釋: 1 <--- / \ 2 3 <--- \ \ 5 4 <---
分析：1嫉拐、深度優(yōu)先遍歷；2魁兼、層序遍歷（2種寫法婉徘，本質(zhì)上其實一樣）。
Python 代碼：
# 199. 二叉樹的右視圖
# 給定一棵二叉樹，想象自己站在它的右側(cè)盖呼，按照從頂部到底部的順序儒鹿，返回從右側(cè)所能看到的節(jié)點值。
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
（本節(jié)完）
