第N叉樹的三種遍歷(層次遍歷、前序遍歷、后序遍歷)目錄題目鏈接：1、層次遍歷2、前序遍歷3、后序遍歷

題目鏈接：

590.N叉樹的后序遍歷

429.N叉樹的層序遍歷

598.N叉樹的前序遍歷

1、層次遍歷

"""

#DefinitionforaNode.

classNode:

def__init__(self,val=None,children=None):

self.val=val

self.children=children

classSolution:

deflevelOrder(self,root:'Node')-List[List[int]]:

ifnotroot:

return[]

queue=collections.deque()

queue.append(root)

res=[]

whilequeue:

size=len(queue)

temp=[]

for_inrange(size):

node=queue.popleft()

temp.append(node.val)

ifnode.children:

queue.extend(node.children)

res.append(temp)

returnres

2、前序遍歷

前序遍歷就是從左至右，先根后孩子；遞歸比較簡單，迭代法的話需要借助一個輔助棧，把每個節(jié)點的孩子都壓入棧中；

"""

#DefinitionforaNode.

classNode:

def__init__(self,val=None,children=None):

self.val=val

self.children=children

classSolution:

defpreorder(self,root:'Node')-List[int]:

ifnotroot:

return[]

#迭代法

stack,output=[root,],[]

whilestack:

root=stack.pop()

output.append(root.val)

stack.extend(root.children[::-1])

returnoutput

#遞歸法

res=[]

defhelper(root):

ifnotroot:

return

res.append(root.val)

forchildreninroot.children:

helper(children)

helper(root)

returnres

3、后序遍歷

在后序遍歷中，我們會先遍歷一個節(jié)點的所有子節(jié)點，再遍歷這個節(jié)點本身。例如當前的節(jié)點為u，它的子節(jié)點為v1,v2,v3時，那么后序遍歷的結(jié)果為[childrenofv1],v1,[childrenofv2],v2,[childrenofv3],v3,u，其中[childrenofvk]表示以vk為根節(jié)點的子樹的后序遍歷結(jié)果（不包括vk本身）。我們將這個結(jié)果反轉(zhuǎn)，可以得到u,v3,[childrenofv3],v2,[childrenofv2],v1,[childrenofv1]，其中[a]表示[a]的反轉(zhuǎn)。此時我們發(fā)現(xiàn)，結(jié)果和前序遍歷非常類似，只不過前序遍歷中對子節(jié)點的遍歷順序是v1,v2,v3，而這里是v3,v2,v1。

"""

#DefinitionforaNode.

classNode:

def__init__(self,val=None,children=None):

self.val=val

self.children=children

classSolution:

defpostorder(self,root:'Node')-List[int]:

ifnotroot:

return[]

#后續(xù)遍歷是先遍歷一個節(jié)點的孩子節(jié)點,在去遍歷這個節(jié)點本身

result=[]

defpostHelper(root):

ifnotroot:

returnNone

children=root.children

f