什么是后序遍历？

推荐答案

后序遍历（Postorder Traversal）是二叉树遍历的一种方式，遍历顺序为：左子树 -> 右子树 -> 根节点。即先访问左子树，再访问右子树，最后访问根节点。

本题详细解读

1. 后序遍历的定义

后序遍历是一种深度优先遍历（DFS）的方式，适用于二叉树或树结构。它的遍历顺序是：

1. 遍历左子树
2. 遍历右子树
3. 访问根节点

2. 后序遍历的递归实现

后序遍历可以通过递归的方式实现，代码示例如下（以二叉树为例）：

// www.javascriptcn.com code example
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorderTraversal(root):
    result = []
    def traverse(node):
        if not node:
            return
        traverse(node.left)  # 遍历左子树
        traverse(node.right)  # 遍历右子树
        result.append(node.val)  # 访问根节点
    traverse(root)
    return result

3. 后序遍历的迭代实现

后序遍历也可以通过迭代的方式实现，通常使用栈来辅助遍历。以下是迭代实现的代码示例：

// www.javascriptcn.com code example
def postorderTraversal(root):
    if not root:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return result[::-1]  # 反转结果，得到后序遍历顺序

4. 后序遍历的应用场景

后序遍历常用于以下场景：

• 表达式树的求值：后序遍历可以用于计算表达式树的值，因为操作符在操作数之后访问。
• 删除二叉树：在删除二叉树时，需要先删除子节点，再删除根节点，后序遍历符合这一需求。
• 文件系统的遍历：在遍历文件系统时，可能需要先处理子目录，再处理父目录。

5. 后序遍历的时间复杂度

后序遍历的时间复杂度为 O(n)，其中 n 是二叉树中节点的数量。每个节点都会被访问一次。空间复杂度取决于树的深度，递归实现的空间复杂度为 O(h)，其中 h 是树的高度。