什么是中序遍历？

推荐答案

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

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

中序遍历常用于二叉搜索树（BST），因为它会按照从小到大的顺序访问节点。

本题详细解读

1. 中序遍历的定义

中序遍历是一种深度优先遍历（DFS）的方式，适用于二叉树。它的核心思想是优先访问左子树，然后访问根节点，最后访问右子树。这种遍历方式可以保证在二叉搜索树中，节点的访问顺序是升序的。

2. 中序遍历的递归实现

以下是中序遍历的递归实现代码（以Python为例）：

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

3. 中序遍历的迭代实现

中序遍历也可以使用栈来实现迭代版本，以下是迭代实现的代码：

// www.javascriptcn.com code example
def inorderTraversal(root):
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left  # 遍历左子树
        current = stack.pop()
        result.append(current.val)  # 访问根节点
        current = current.right  # 遍历右子树
    return result

4. 中序遍历的应用

• 二叉搜索树（BST）：中序遍历二叉搜索树会得到一个升序的节点值序列。
• 表达式树：中序遍历表达式树可以得到中缀表达式。
• 调试和验证：中序遍历可以用于验证二叉树的结构是否正确。

5. 时间复杂度与空间复杂度

• 时间复杂度：O(n)，其中 n 是二叉树中的节点数。每个节点被访问一次。
• 空间复杂度：递归实现的空间复杂度为 O(h)，其中 h 是树的高度；迭代实现的空间复杂度为 O(n)，因为需要使用栈来存储节点。