这是一个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
我是一名优秀的程序员,十分优秀!