N叉树的后序遍历 [英] Postorder traversal of an n ary tree
本文介绍了N叉树的后序遍历的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我需要以下代码的帮助才能回答。我正在尝试使用堆栈而不是递归在n元树上执行后序遍历,因为Python有1000次递归的限制。我在Geek上为Geek找到了同样"https://www.geeksforgeeks.org/iterative-preorder-traversal-of-a-n-ary-tree/"的预购遍历代码。但我不能把它改成邮购。任何帮助都是最好的。
推荐答案
以下是iteration
我使用的stack
版本:
class TreeNode:
def __init__(self, x):
self.val = x
self.children = []
def postorder_traversal_iteratively(root: 'TreeNode'):
if not root:
return []
stack = [root]
# used to record whether one child has been visited
last = None
while stack:
root = stack[-1]
# if current node has no children, or one child has been visited, then process and pop it
if not root.children or last and (last in root.children):
'''
add current node logic here
'''
print(root.val, ' ', end='')
stack.pop()
last = root
# if not, push children in stack
else:
# push in reverse because of FILO, if you care about that
for child in root.children[::-1]:
stack.append(child)
测试代码&;输出:
n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6)
n7 = TreeNode(7)
n8 = TreeNode(8)
n9 = TreeNode(9)
n10 = TreeNode(10)
n11 = TreeNode(11)
n12 = TreeNode(12)
n13 = TreeNode(13)
n1.children = [n2, n3, n4]
n2.children = [n5, n6]
n4.children = [n7, n8, n9]
n5.children = [n10]
n6.children = [n11, n12, n13]
postorder_traversal_iteratively(n1)
可视化n叉树和输出:
1
/ |
/ |
2 3 4
/ / |
5 6 7 8 9
/ / |
10 11 12 13
# output: 10 5 11 12 13 6 2 3 7 8 9 4 1
做后序的另一个想法是更改结果,例如将结果插入到Head。
效率较低,但很容易编码。您可以在here
中找到版本我已经在我的GitHub中总结了类似上面的算法。 如果您对以下内容感兴趣,请观看: https://github.com/recnac-itna/Code_Templates
这篇关于N叉树的后序遍历的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文