N叉树的三种遍历(层次遍历、前序遍历、后序遍历)
时间：2022-07-16 09:41:51 | 栏目：C代码 | 点击：次
题目链接：
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 res
2、前序遍历
前序遍历就是从左至右，先根后孩子；递归比较简单，迭代法的话需要借助一个辅助栈，把每个节点的孩子都压入栈中；
"""
# 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 res
3、后序遍历
在后序遍历中，我们会先遍历一个节点的所有子节点，再遍历这个节点本身。例如当前的节点为 u，它的子节点为 v1, v2, v3 时，那么后序遍历的结果为 [children of v1], v1, [children of v2], v2, [children of v3], v3, u，其中 [children of vk] 表示以 vk 为根节点的子树的后序遍历结果（不包括 vk 本身）。我们将这个结果反转，可以得到 u, v3, [children of v3]', v2, [children of v2]', v1, [children of v1]'，其中 [a]' 表示 [a] 的反转。此时我们发现，结果和前序遍历非常类似，只不过前序遍历中对子节点的遍历顺序是 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 []
#后续遍历是先遍历一个节点的孩子节点,在去遍历这个节点本身
#递归
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]
总结：N叉树和二叉树的差别不是很多，唯一的差别就是孩子很多不需要去判断左右孩子了。