N叉树的三种遍历:层次遍历、前序遍历、后序遍历
程序员文章站
2022-06-16 08:37:20
...
题目链接:
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叉树和二叉树的差别不是很多,唯一的差别就是孩子很多不需要去判断左右孩子了。
推荐阅读
-
1086 Tree Traversals Again (25 分)(二叉树的遍历)
-
JavaScript实现多叉树的递归遍历和非递归遍历算法操作示例
-
Python利用前序和中序遍历结果重建二叉树的方法
-
C语言实现线索二叉树的前中后创建和遍历详解
-
python数据结构之二叉树的遍历实例
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
Python实现二叉树结构与进行二叉树遍历的方法详解