解题思路：
层序遍历的顺序为从上到下，从左到右依次遍历。
从上到下是通过访问根节点的左右子树遍历。
从左到右是记录每一层的节点个数，以下代码的 level 就是这个作用，这里使用了双端队列是为了推广性，如下题 103， z 形循环记录每层的结点，用列表也是可以的。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
#加入根节点
queue = [root]
res = []
while queue:
#每层节点
level = deque()
size = len(queue)
for _ in range(size):
cur = queue.pop(0)
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
if level:
res.append(list(level))
return res
103. 二叉树的锯齿形层序遍历
解题思路：
定义一个 flag作为记录，奇数正向，偶数逆向。
双端队列可以很方便的前后增加元素。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
#加入根节点
queue = [root]
res = []
flag = True
while queue:
#每层节点
level = deque() #deque
size = len(queue)
for _ in range(size):
cur = queue.pop(0)
if flag:
level.append(cur.val)
else:
level.appendleft(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
if level:
res.append(list(level))
flag = not flag
return res
107. 二叉树的层序遍历 II
解题思路：
如题 102，这道题只颠倒每层记录的节点顺序就可以。
注意一点，相信很多人想用 reverse() 直接颠倒列表顺序，但这个函数调用后是不会返回列表的，所以还是用切片的方式来颠倒每层节点的顺序。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
#加入根节点
queue = [root]
res = []
while queue:
#每层节点
level = deque()
size = len(queue)
for _ in range(size):
cur = queue.pop(0)
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
if level:
res.append(list(level))
return res[::-1]
111. 二叉树的最小深度
解题思路：
BFS 记录每层的高度即可，然后选择最小深度即可。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
#加入根节点
queue = [root]
depth = 1
while queue:
size = len(queue)
for _ in range(size):
cur = queue.pop(0)
if not cur.left and not cur.right:
return depth
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
depth += 1
return depth
DFS 也可以解决这道题，如下注释。
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
left = self.minDepth(root.left)
right = self.minDepth(root.right)
if not root.left and not root.right: #没有子节点为叶子节点
return 1
min_depth = 0xffffff
#分别对比左右子树，选择最短路径上的节点个数
if root.left:
min_depth = min(left,min_depth)
if root.right:
min_depth = min(right, min_depth)
return min_depth + 1
另外一种 DFS写法，本质是一样的，
额外列举一个函数的好处是，
内部函数的 base case 可以直接用于记录空节点的返回数值，用于从
不需要额外的变量储存用于比较的 min_depth。
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: #判断根节点
return 0
def dfs(node):
if not node: # base case 记录一个数值用于比较
return float("inf")
elif not node.left and not node.right:
return 1
return min(dfs(node.left) , dfs(node.right)) + 1
return dfs(root)
BFS 算法和 DFS算法的一大区别就是，BFS 第一次搜索到的结果是最优的，但是空间复杂度高。
DFS 时间复杂较高，因为 DFS 要探索所有的节点后才能知道哪个结果是最优的。
