102. 二叉樹的層序遍歷
題目來源：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
題目
給你一個(gè)二叉樹烤惊，請你返回其按 層序遍歷 得到的節(jié)點(diǎn)值。 （即逐層地呼畸，從左到右訪問所有節(jié)點(diǎn)）。
示例：
二叉樹：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其層次遍歷結(jié)果：
[
[3],
[9,20],
[15,7]
]
解題思路
思路：廣度優(yōu)先搜索
本題，我們使用廣度優(yōu)先搜索的思路來解決。
廣度優(yōu)先搜索（BFS）任柜，它是按照層進(jìn)行搜索的。題目中要求沛厨，按層序遍歷得到所需的節(jié)點(diǎn)宙地。那么這里就跟 BFS 訪問的方式吻合。
在這里逆皮，我們借助隊(duì)列宅粥，保存每層的所有節(jié)點(diǎn)，然后每次把隊(duì)列里所有的節(jié)點(diǎn)都進(jìn)行出隊(duì)操作电谣。出隊(duì)這里需要注意秽梅，保存每層所有節(jié)點(diǎn)的時(shí)候，這里先可以標(biāo)記每層的節(jié)點(diǎn)數(shù)剿牺，那么在出隊(duì)的時(shí)候风纠，循環(huán)遍歷的次數(shù)就等于當(dāng)前層數(shù)的節(jié)點(diǎn)數(shù)。
此時(shí)遍歷每層節(jié)點(diǎn)時(shí)牢贸，如果當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)非空時(shí)竹观，再次加入隊(duì)列。循環(huán)操作，這樣每層都能夠被遍歷臭增，隊(duì)列為空時(shí)懂酱，就能得到想要的結(jié)果。
具體的代碼如下誊抛。
代碼實(shí)現(xiàn)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
# 先處理特殊情況
if not root:
return []
# 返回結(jié)果
res = []
from collections import deque
# 定義隊(duì)列
queue = deque()
# 將根節(jié)點(diǎn)入隊(duì)
queue.append(root)
# 隊(duì)列不為空列牺，表達(dá)式二叉樹還有節(jié)點(diǎn)，循環(huán)遍歷
while queue:
# 先標(biāo)記每層的節(jié)點(diǎn)數(shù)
size = len(queue)
# 定義變量拗窃，記錄每層節(jié)點(diǎn)值
level = []
# 這里開始遍歷當(dāng)前層的節(jié)點(diǎn)
for _ in range(size):
# 出隊(duì)
node = queue.popleft()
# 先將當(dāng)前節(jié)點(diǎn)的值存儲(chǔ)
level.append(node.val)
# 節(jié)點(diǎn)的左右節(jié)點(diǎn)非空時(shí)瞎领，入隊(duì)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
# 添加每層的節(jié)點(diǎn)值列表
res.append(level)
return res
實(shí)現(xiàn)結(jié)果
以上就是使用廣度優(yōu)先搜索，借助隊(duì)列先入先出的性質(zhì)随夸，逐層遍歷九默，得到所需求的解，進(jìn)而解決《102. 二叉樹的層序遍歷》問題的主要內(nèi)容宾毒。
歡迎關(guān)注微信公眾號(hào)《書所集錄》
