日野弥生：勉強しよう
LeetCode 590 - N 叉树的后序遍历
发表于2025年03月28日
本题递归法和N叉树的前序遍历思路基本相同，只是代码顺序稍加改变即可。
class Solution:
def postorder(self, root: 'Node') -> List[int]:
result = []
def postorderImpl(root: 'Node'):
if not root:
return
for chd in root.children:
postorderImpl(chd)
result.append(root.val)
postorderImpl(root)
return result迭代法的思路和二叉树也类似，只是需要注意进栈的子树的顺序，以及进栈时需要给出是否需要遍历所有子树的标记。
class Solution:
def postorder(self, root: 'Node') -> List[int]:
result = []
stack = deque()
while root or stack:
if root:
# 根节点进栈，所有子树后面已经进栈，所以标记为已经遍历
stack.append([root, True])
if root.children:
# 把所有子树都进栈后出栈第一个子树
for i in reversed(root.children):
# 子树全部进栈，但是都没有遍历过子节点，标记为False
stack.append([i, False])
item = stack.pop()
root = item[0]
else:
# 遍历到叶子时，把当且节点值置空
root = None
elif stack:
item = stack.pop()
# 如果标记为False，说明子树没遍历过，继续循环进栈
root = item[0]
if item[1]:
# 当且仅当取出来的节点无需遍历子树时，才输出此节点
result.append(root.val)
root = None
return result