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