中序遍历（In-order Traversal）

一句话说明

中序遍历的顺序是“左、根、右”，它最有价值的地方在于：BST 的中序结果天然有序。

顺序先记死

左 -> 根 -> 右

示例：

      4
     / \
    2   6
   / \ / \
  1  3 5  7

中序结果：

[1, 2, 3, 4, 5, 6, 7]

为什么它和 BST 天然契合

BST 满足：

• 左边全都更小
• 右边全都更大

所以按“左、根、右”访问，得到的就是从小到大的有序序列。
这也是下面这些题的基础：

• 验证 BST
• BST 第 K 小
• BST 转有序数组

Go 代码：递归中序

func InorderTraversal(root *TreeNode) []int {
    result := []int{}
 
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        result = append(result, node.Val)
        dfs(node.Right)
    }
 
    dfs(root)
    return result
}

Go 代码：栈实现中序

func InorderTraversalIterative(root *TreeNode) []int {
    result := []int{}
    stack := []*TreeNode{}
 
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
 
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, root.Val)
        root = root.Right
    }
 
    return result
}

迭代写法到底在模拟什么

它在模拟这件事：

• 一路往左走到底
• 左边都处理完以后，轮到当前节点
• 然后转去右子树

也就是说，栈里存的是“还没处理自己，但左边已经在路上的祖先链”。

常见题型

• 验证 BST
• 第 k 小元素
• BST 最小绝对差
• BST 转有序链表 / 有序数组

易错点

中序遍历最容易错的地方

• 访问完一个节点后，别忘了转去它的右子树。
• 中序在 BST 上很有用，但在普通二叉树上不一定有特殊含义。
• 验证 BST 时判断的是“严格递增”，不是“非递减”。

复杂度

实现方式	时间复杂度	空间复杂度
递归	O(n)	O(h)
栈迭代	O(n)	O(h)

相关主题

• 前序遍历
• 后序遍历
• 验证 BST
• 树算法

---

返回：树算法 | 算法学习导航