102.二叉樹的層序遍歷
難度：中等
題目：
給你一個二叉樹臊泰，請你返回其按 層序遍歷 得到的節(jié)點值何陆。 （即逐層地厅各，從左到右訪問所有節(jié)點）汽畴。
示例：
示例：
二叉樹：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其層序遍歷結果：
[
[3],
[9,20],
[15,7]
]
分析
BFS 解題分析
對于二叉樹的層序遍歷，一般都是使用BFS配合隊列完成解題房资。
- 使用隊列保存每層的所有節(jié)點（初始先入隊根節(jié)點）
- 每次講隊列中的元素循環(huán)出隊蜕劝，獲取該元素對應的val值
- 再把每個元素的非空左右子節(jié)點進入隊列
- 循環(huán)2、3轰异，即可得到每層的遍歷岖沛。
DFS 解題分析
二叉樹的前、中搭独、后 順序遍歷婴削，一般最簡單的是使用深度優(yōu)先，但層序遍歷也可以通過DFS來解題牙肝。
麻煩一些的就是我們需要在DFS層級遍歷的時候唉俗，根據(jù)當前深度進行保存，這里由于返回列表配椭，所以
使用defaultdict來構造特殊的Hash表更為快捷虫溜。由于字典的key值為深度，是存在默認排序的股缸，
所以遞歸返程回放回即可衡楞。
下面來分別看看一下兩種解題...
解題1 廣度優(yōu)先算法：
from collections import deque
class Solution:
def levelOrder(self, root):
ret = []
queue = deque([root])
while queue:
tmp = []
for i in range(len(queue)):
point = queue.popleft()
if point:
tmp.append(point.val)
queue.append(point.left)
queue.append(point.right)
if tmp:
ret.append(tmp)
return ret
解題2 深度優(yōu)先算法：
from collections import defaultdict
class Solution:
def levelOrder(self, root):
ret = defaultdict(list)
def dfs(base, level):
nonlocal ret
if base:
ret[level].append(base.val)
dfs(base.left, level + 1)
dfs(base.right, level + 1)
dfs(root, 0)
return list(ret.values())
歡迎關注我的公眾號: 清風Python，帶你每日學習Python算法刷題的同時敦姻，了解更多python小知識瘾境。
我的個人博客：https://qingfengpython.cn
