什么是前序遍历？

推荐答案

前序遍历（Preorder Traversal）是二叉树遍历的一种方式，其遍历顺序为：根节点 -> 左子树 -> 右子树。具体步骤如下：

1. 访问根节点。
2. 递归地前序遍历左子树。
3. 递归地前序遍历右子树。

前序遍历的结果通常用于表达树的结构，或者用于复制树的结构。

本题详细解读

1. 前序遍历的定义

前序遍历是一种深度优先遍历（DFS）的方式，它首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。这种遍历方式的特点是根节点总是最先被访问。

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 preorderTraversal(root):
    result = []
    def traverse(node):
        if not node:
            return
        result.append(node.val)  # 访问根节点
        traverse(node.left)      # 递归遍历左子树
        traverse(node.right)     # 递归遍历右子树
    traverse(root)
    return result

3. 前序遍历的迭代实现

前序遍历也可以使用栈来实现迭代版本，代码示例如下：

// www.javascriptcn.com code example
def preorderTraversal(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)  # 访问根节点
        if node.right:           # 先将右子节点压栈
            stack.append(node.right)
        if node.left:            # 再将左子节点压栈
            stack.append(node.left)
    return result

4. 前序遍历的应用场景

• 树的复制：前序遍历可以用于复制一棵树的结构。
• 表达式树：在表达式树中，前序遍历可以得到前缀表达式。
• 序列化与反序列化：前序遍历的结果可以用于序列化二叉树，便于存储和传输。

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

前序遍历的时间复杂度为 O(n)，其中 n 是树中节点的数量。每个节点都会被访问一次。

6. 前序遍历的空间复杂度

• 递归实现：空间复杂度为 O(h)，其中 h 是树的高度。递归调用栈的深度取决于树的高度。
• 迭代实现：空间复杂度为 O(h)，其中 h 是树的高度。栈的最大深度也取决于树的高度。

通过以上内容，可以全面理解前序遍历的定义、实现方式及其应用场景。