目录

二叉搜索树与中序遍历

二叉搜索树（BST）和中序遍历是一对天然的搭档，它们之间存在着双向的等价关系：

以下两道题恰好从两个方向展示了这个关系。

方向一：BST → 有序序列（统计频次）

501. Find Mode in Binary Search Tree

题目要求找出 BST 中出现频率最高的值（mode），且尽量不使用额外空间。

思路

BST 的中序遍历结果是有序的，这意味着相同的值一定连续出现。我们只需要在中序遍历的过程中，维护一个"滑动窗口"来统计当前值的出现次数：

var traverse func(p *TreeNode)
traverse = func(p *TreeNode) {
    if p == nil {
        return
    }

    traverse(p.Left)

    // 遇到新值，重置窗口
    if candidate == nil || candidate.Val != p.Val {
        cnt = 0
        candidate = p
    }

    cnt++
    if cnt > maxFreq {
        result = []int{candidate.Val}
        maxFreq = cnt
    } else if cnt == maxFreq {
        result = append(result, candidate.Val)
    }

    traverse(p.Right)
}

关键点：

方向二：有序序列 → BST（中序构建）

109. Convert Sorted List to Binary Search Tree

题目要求将有序链表转换为一棵高度平衡的二叉搜索树。

思路一：分治法找中点（直观解法）

func sortedListToBST(head *ListNode) *TreeNode {
    if head == nil {
        return nil
    }

    l, r := splitList(head)
    left := sortedListToBST(l)
    right := sortedListToBST(r.Next)

    return &TreeNode{
        Val:   r.Val,
        Left:  left,
        Right: right,
    }
}

func splitList(head *ListNode) (l, r *ListNode) {
    if head == nil || head.Next == nil {
        return nil, head
    }

    dummy := &ListNode{Next: head}
    slow, fast := dummy, dummy
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    l, r = head, slow.Next
    slow.Next = nil // 断开链表
    return
}

思路是：快慢指针找到链表中点作为根节点，然后递归构建左右子树。每次递归都需要扫描链表找中点，时间复杂度 O(n log n)。

思路二：模拟中序遍历（优化版）

更优雅的方式是利用中序遍历的逆过程：用一个全局指针按中序顺序"填充" BST 的节点。

func sortedListToBST(head *ListNode) *TreeNode {
    // 先计算链表长度
    n := 0
    for p := head; p != nil; p = p.Next {
        n++
    }

    cur := head
    var inorderBuild func(l, r int) *TreeNode
    inorderBuild = func(l, r int) *TreeNode {
        if l > r {
            return nil
        }

        mid := l + (r-l)/2

        // 中序遍历：先构建左子树
        left := inorderBuild(l, mid-1)

        // "访问"当前节点——此时 cur 正好指向当前应该放置的节点
        node := &TreeNode{Val: cur.Val}
        cur = cur.Next

        // 再构建右子树
        right := inorderBuild(mid+1, r)

        node.Left = left
        node.Right = right
        return node
    }

    return inorderBuild(0, n-1)
}

关键点：

跟踪示例：[1, 2, 3, 4, 5]（n=5）

初始 cur 指向链表头 1，调用 inorderBuild(0, 4)：

inorderBuild(0, 4)       mid=2
  ├─ inorderBuild(0, 1)  mid=0
  │   ├─ 左: (0, -1) → nil
  │   ├─ ★ 访问节点: cur.Val = 1, cur = cur.Next → cur 指向 2
  │   └─ 右: (1, 1) → mid=1
  │       ├─ 左: (1, 0) → nil
  │       ├─ ★ 访问节点: cur.Val = 2, cur = cur.Next → cur 指向 3
  │       └─ 右: (2, 1) → nil
  │       └─ 返回 Val=2
  │   └─ 返回 Val=1（Left=nil, Right=节点2）
  ├─ ★ 访问节点: cur.Val = 3, cur = cur.Next → cur 指向 4
  └─ 右: (3, 4) → mid=3
      ├─ 左: (3, 2) → nil
      ├─ ★ 访问节点: cur.Val = 4, cur = cur.Next → cur 指向 5
      └─ 右: (4, 4) → mid=4
          ├─ 左: (4, 3) → nil
          ├─ ★ 访问节点: cur.Val = 5, cur = cur.Next → nil
          └─ 右: (5, 4) → nil
          └─ 返回 Val=5
      └─ 返回 Val=4（Left=nil, Right=节点5）
  └─ 返回 Val=3（Left=节点1, Right=节点4）

最终树结构：

      3
     / \
    1   4
     \   \
      2   5

核心原理：为什么能这样？

机制作用
索引范围决定树的骨架（谁是谁的左/右孩子），和值无关
中序递归结构左→根→右的递归顺序，恰好和链表从头到尾的顺序一致
cur = cur.Next每"访问"一个节点就推进链表指针，中序递归的"访问时刻"和链表顺序完美对齐

换句话说，递归调用的"形状"由索引决定，而递归的"时机"由 cur 的推进自动匹配。这本质上是用递归调用的控制流来模拟中序遍历，让链表数据自然流入正确的位置。这是它比分治法（每次递归需要 O(n) 找中点，总 O(n log n)）更优的根本原因。

总结：BST 与中序遍历的等价关系

方向应用
BST → 有序序列中序遍历 BSTFind Mode（501）、验证 BST、求第 k 小
有序序列 → BST模拟中序遍历构建Sorted List to BST（109）、Sorted Array to BST

两条核心结论：

  1. BST 的中序遍历就是有序序列，这是 BST 最重要的性质。遇到 BST 上的"顺序相关"问题，优先考虑中序遍历。
  2. 有序序列构建 BST 可以通过模拟中序遍历完成，不需要每次都找中点。先确定树的"骨架"（索引范围），再按中序填充值，时间和代码上都更优。