N叉樹(shù)的三種遍歷(層次遍歷、前序遍歷、后序遍歷)
題目鏈接：
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)的子樹(shù)的后序遍歷結(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叉樹(shù)和二叉樹(shù)的差別不是很多，唯一的差別就是孩子很多不需要去判斷左右孩子了。
到此這篇關(guān)于N叉樹(shù)的三種遍歷(層次遍歷、前序遍歷、后序遍歷)的文章就介紹到這了,更多相關(guān)N叉樹(shù)的三種遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
vscode和cmake編譯多個(gè)C++文件的實(shí)現(xiàn)方法
這篇文章主要介紹了vscode和cmake編譯多個(gè)C++文件的實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
這篇文章主要介紹了掌握C++編程中反斜杠續(xù)行符的使用方法,包括取反斜杠的本意的方法等基本知識(shí)點(diǎn),需要的朋友可以參考下2016-01-01
本文包括了對(duì)C++類的6個(gè)默認(rèn)成員函數(shù)中的賦值運(yùn)算符重載和取地址和const對(duì)象取地址操作符的重載。運(yùn)算符是程序中最最常見(jiàn)的操作，例如對(duì)于內(nèi)置類型的賦值我們直接使用=賦值即可，因?yàn)檫@些編譯器已經(jīng)幫我們做好了，但是對(duì)象的賦值呢？能直接賦值嗎2022-06-06
C語(yǔ)言開(kāi)源庫(kù)iniparser解析ini文件的方法
INI（Initialization?File）文件是一種簡(jiǎn)單直觀的數(shù)據(jù)存儲(chǔ)格式,常用于配置應(yīng)用程序的初始化設(shè)置,使用?iniparser?庫(kù)的應(yīng)用程序可以很方便地讀取和解析INI文件中的配置信息,大大簡(jiǎn)化了對(duì)配置文件的處理工作,降低了程序的開(kāi)發(fā)復(fù)雜度,感興趣的的朋友跟隨小編一起看看吧2024-04-04
C++跳轉(zhuǎn)語(yǔ)句之Goto對(duì)變量定義的影響詳解
goto語(yǔ)句也被稱為無(wú)條件轉(zhuǎn)移語(yǔ)句，這篇文章主要介紹了C++跳轉(zhuǎn)語(yǔ)句之Goto對(duì)變量定義的影響，文中通過(guò)示例代碼解文字介紹的很詳細(xì)，相信對(duì)大家的理解和學(xué)習(xí)具有一定的參考借鑒價(jià)值，有需要的朋友們下面跟著小編一起來(lái)學(xué)習(xí)學(xué)習(xí)吧。2016-11-11
C語(yǔ)言中棧和隊(duì)列實(shí)現(xiàn)表達(dá)式求值的實(shí)例
這篇文章主要介紹了C語(yǔ)言中棧和隊(duì)列實(shí)現(xiàn)表達(dá)式求值的實(shí)例的相關(guān)資料,這里主要是對(duì)數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的理解和應(yīng)用，需要的朋友可以參考下2017-08-08
C++智能指針shared_ptr與weak_ptr的實(shí)現(xiàn)分析
shared_ptr是一個(gè)標(biāo)準(zhǔn)的共享所有權(quán)的智能指針，允許多個(gè)指針指向同一個(gè)對(duì)象，定義在 memory 文件中，命名空間為 std，這篇文章主要介紹了C++ 中 shared_ptr weak_ptr,需要的朋友可以參考下2022-09-09
C語(yǔ)言中對(duì)字母進(jìn)行大小寫轉(zhuǎn)換的簡(jiǎn)單方法
這篇文章主要介紹了C語(yǔ)言中對(duì)字母進(jìn)行大小寫轉(zhuǎn)換的簡(jiǎn)單方法,是C語(yǔ)言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-08-08
C語(yǔ)言實(shí)現(xiàn)學(xué)生管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)學(xué)生管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02