这里有一个iteration
版本与stack
I used:
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
后序的另一个想法是改变结果,例如将结果插入到头部。
它效率较低,但易于编码。你可以找到一个版本here https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45551/Preorder-Inorder-and-Postorder-Iteratively-Summarization
我已经总结了code templates
对于像我的 github 中上面这样的算法。
如果您有兴趣,请观看:https://github.com/recnac-itna/Code_Templates https://github.com/recnac-itna/Code_Templates