解題思路：
層序遍歷的順序為從上到下，從左到右依次遍歷。
從上到下是通過訪問根節點的左右子樹遍歷。
從左到右是記錄每一層的節點個數，以下代碼的 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
解題思路：
定義一個 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
解題思路：
如題 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]
解題思路：
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 要探索所有的節點後才能知道哪個結果是最優的。
