本文共 1651 字，大约阅读时间需要 5 分钟。

后序遍历的实现

后序遍历是一种树遍历方式，按照从左到右的顺序访问左子树、右子树，然后访问根节点。这种遍历方式常用于计算某些树的特性，如计算子树的大小、和等。

递归方法

递归方法是解决后序遍历问题的直观方式。递归函数遍历每个节点的子节点，然后将节点值添加到结果列表中。具体步骤如下：

代码示例：

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
class Solution:
    def postorder(self, root):
        result = []
        def helper(node):
            if not node:
                return
            for child in node.children:
                helper(child)
            result.append(node.val)
        helper(root)
        return result

解释：helper函数递归遍历每个节点的子节点，确保先处理左子树，再处理右子树。处理完所有子节点后，添加当前节点的值到结果列表中。

迭代方法

迭代方法使用栈来模拟递归过程，避免递归深度过大的问题。具体步骤如下：

代码示例：

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
class Solution:
    def postorder(self, root):
        if not root:
            return []
        result = []
        stack = [(root, False)]
        while stack:
            node, visited = stack.pop()
            if not visited:
                stack.append((node, True))
                for child in reversed(node.children):
                    stack.append((child, False))
            else:
                result.append(node.val)
        return result

解释：栈中每个元素包含节点和一个标志位。未处理时，节点及其子节点被压入栈，标志位设为True时，表示节点已处理，值被添加到结果列表中。通过反转子节点顺序，确保先处理左子树，再处理右子树。

总结

无论是递归方法还是迭代方法，都能有效地实现后序遍历。递归方法简洁明了，但可能存在栈深度限制的问题。迭代方法通过栈模拟了递归过程，避免了递归深度过大的问题，适用于大规模树结构。两种方法都能正确生成树节点的后序遍历结果。