N叉樹的三種遍歷(層次遍歷、前序遍歷、后序遍歷)
題目鏈接：
1、層次遍歷
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
queue = collections.deque()
queue.append(root)
res = []
while queue:
size = len(queue)
temp = []
for _ in range(size):
node = queue.popleft()
temp.append(node.val)
if node.children:
queue.extend(node.children)
res.append(temp)
return res2、前序遍歷
前序遍歷就是從左至右，先根后孩子；遞歸比較簡(jiǎn)單，迭代法的話需要借助一個(gè)輔助棧，把每個(gè)節(jié)點(diǎn)的孩子都?jí)喝霔Ｖ校?/strong>
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if not root:
return []
#迭代法
stack, output = [root, ], []
while stack:
root = stack.pop()
output.append(root.val)
stack.extend(root.children[::-1])
return output
#遞歸法
res = []
def helper(root):
if not root:
return
res.append(root.val)
for children in root.children:
helper(children)
helper(root)
return res3、后序遍歷
在后序遍歷中，我們會(huì)先遍歷一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)，再遍歷這個(gè)節(jié)點(diǎn)本身。例如當(dāng)前的節(jié)點(diǎn)為 u，它的子節(jié)點(diǎn)為 v1, v2, v3 時(shí)，那么后序遍歷的結(jié)果為 [children of v1], v1, [children of v2], v2, [children of v3], v3, u，其中 [children of vk] 表示以 vk 為根節(jié)點(diǎn)的子樹的后序遍歷結(jié)果（不包括 vk 本身）。我們將這個(gè)結(jié)果反轉(zhuǎn)，可以得到 u, v3, [children of v3]', v2, [children of v2]', v1, [children of v1]'，其中 [a]' 表示 [a] 的反轉(zhuǎn)。此時(shí)我們發(fā)現(xiàn)，結(jié)果和前序遍歷非常類似，只不過(guò)前序遍歷中對(duì)子節(jié)點(diǎn)的遍歷順序是 v1, v2, v3，而這里是 v3, v2, v1。
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
if not root:
return []
#后續(xù)遍歷是先遍歷一個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn),在去遍歷這個(gè)節(jié)點(diǎn)本身
#遞歸
result = []
def postHelper(root):
if not root:
return None
children = root.children
for child in children:
postHelper(child)
result.append(root.val)
postHelper(root)
return result
#迭代法：輔助棧
res = []
stack = [root,]
while stack:
node = stack.pop()
if node is not None:
res.append(node.val)
for children in node.children:
stack.append(children)
return res[::-1]總結(jié)：N叉樹和二叉樹的差別不是很多，唯一的差別就是孩子很多不需要去判斷左右孩子了。
到此這篇關(guān)于N叉樹的三種遍歷(層次遍歷、前序遍歷、后序遍歷)的文章就介紹到這了,更多相關(guān)N叉樹的三種遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++?多繼承詳情，C++支持多繼承，即允許一個(gè)類同時(shí)繼承多個(gè)類。只有C++等少數(shù)語(yǔ)言支持多繼承，下面我們就來(lái)看看具體的多繼承介紹吧,需要的朋友可以參考一下2022-03-03
這篇文章主要介紹了c++11 atomic的使用詳解，幫助大家更好的理解和學(xué)習(xí)使用c++，感興趣的朋友可以了解下2021-02-02
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)通訊錄功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
Qt中PaintEvent繪制實(shí)時(shí)波形圖的實(shí)現(xiàn)示例
本文主要介紹了Qt中PaintEvent繪制實(shí)時(shí)波形圖的實(shí)現(xiàn)示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
C語(yǔ)言中QString與QByteArray互相轉(zhuǎn)換的方法
本文主要介紹了C語(yǔ)言中QString與QByteArray互相轉(zhuǎn)換的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05
基于C語(yǔ)言編寫一個(gè)簡(jiǎn)單的抽卡小游戲
這篇文章主要為大家介紹了如何利用C語(yǔ)言實(shí)現(xiàn)原神抽卡的小游戲，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-04-04
利用Debug調(diào)試代碼解決0xC0000005:?讀取位置?0x0000000000000000?時(shí)發(fā)生訪問(wèn)沖突問(wèn)
這篇文章主要介紹了利用Debug調(diào)試代碼解決0xC0000005:?讀取位置?0x0000000000000000?時(shí)發(fā)生訪問(wèn)沖突,本文給大家分享完美解決方案，需要的朋友可以參考下2023-03-03
C語(yǔ)言使用posix正則表達(dá)式庫(kù)的實(shí)現(xiàn)
在C語(yǔ)言中,你可以使用 POSIX 正則表達(dá)式庫(kù)（regex.h）來(lái)進(jìn)行正則表達(dá)式的模式匹配,本文主要介紹了C語(yǔ)言使用posix正則表達(dá)式庫(kù)的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2023-12-12
缺省參數(shù)是聲明或定義函數(shù)時(shí)為函數(shù)的參數(shù)指定一個(gè)默認(rèn)值。本文就詳細(xì)的介紹了一下C++缺省參數(shù)的具體使用，具有一定的參考價(jià)值，感興趣的可以了解一下2022-01-01
最近將項(xiàng)目改為跨平臺(tái)，于是音頻模塊從微軟的XAudio2改用OpenAL庫(kù)。之前使用MSDN的代碼，所以現(xiàn)在改為了C++標(biāo)準(zhǔn)的寫法，適用性更廣2022-09-09