層序遍歷
層序遍歷一個(gè)二叉樹(shù)。就是從左到右一層一層的去遍歷二叉樹(shù)。需要借用一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)即隊(duì)列來(lái)實(shí)現(xiàn)，隊(duì)列先進(jìn)先出，符合一層一層遍歷的邏輯，而用棧先進(jìn)后出適合模擬深度優(yōu)先遍歷也就是遞歸的邏輯。
而這種層序遍歷方式就是圖論中的廣度優(yōu)先遍歷，只不過(guò)應(yīng)用在二叉樹(shù)上。
已刷（都可以通過(guò)層次遍歷實(shí)現(xiàn)）：
226.翻轉(zhuǎn)二叉樹(shù)
- 對(duì)稱二叉樹(shù)
102.二叉樹(shù)的層序遍歷
107.二叉樹(shù)的層次遍歷II
199.二叉樹(shù)的右視圖
637.二叉樹(shù)的層平均值
429.N叉樹(shù)的層序遍歷
515.在每個(gè)樹(shù)行中找最大值
116.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針
117.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針I(yè)I
104.二叉樹(shù)的最大深度
111.二叉樹(shù)的最小深度
222.完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
層次遍歷代碼模板
class Solution:
"""二叉樹(shù)層序遍歷迭代解法"""
def levelOrder(self, root: TreeNode) -> List[List[int]]:
results = []
if not root:
return results
from collections import deque
que = deque([root])
while que:
size = len(que)
result = []
for _ in range(size):
cur = que.popleft()
result.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
results.append(result)
return results
# 遞歸法
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
def helper(root, depth):
if not root: return []
if len(res) == depth: res.append([]) # start the current depth
res[depth].append(root.val) # fulfil the current depth
if root.left: helper(root.left, depth + 1) # process child nodes for the next depth
if root.right: helper(root.right, depth + 1)
helper(root, 0)
return res
