题目

（本题满分 13 分）

假定二叉搜索树使用二叉链表存储，存储结构如下：

typedef struct BSTNode {
    int data;
    struct BSTNode *left, *right;
} BSTNode;

给一棵二叉搜索树 T 和整数 K，查找树中关键字与 K 之差的绝对值最小的所有结点，并输出该绝对值与结点中的关键字。

(1) 给出算法的基本设计思想。（4 分）

(2) 使用 C/C++ 描述算法。（8 分）

解析

(1) 设计思想 [4 分]

关键洞察：BST 中离 K 最近的关键字最多只有两个。把树中所有关键字放到中序序列里就是有序数组，K 在数轴上的位置无非三种：

• K 命中某个结点 → 距离为 0，答案唯一就是 K；
• K 落在两个相邻关键字之间 → 答案就是这两个邻居：比 K 小的最大值（记为 floor） 和 比 K 大的最小值（记为 ceil） 之一，或两者并列；
• K 比整棵树最小值还小（或比最大值还大）→ 只有 ceil（或只有 floor）。

为什么不需要遍历整棵树？一旦确定了 floor 和 ceil，离 K 比这两个邻居更远的所有结点都可以丢掉——不可能更近。BST 的结构刚好支持「沿一条路径」就找出 floor 和 ceil：

• 当前结点 cur->data < K：cur 自身和它的整个左子树都 < K，但右子树里可能藏着比 cur 更接近 K（仍 < K）的结点，所以 cur 是当下最佳的 floor 候选，然后向右走继续找；
• 当前结点 cur->data > K：对称，cur 是当下最佳的 ceil 候选，然后向左走；
• 当前结点 cur->data == K：直接命中，距离 0，结束。

完整流程：

1. 从根开始，用迭代方式下降；下降途中每访问一个结点就按上述规则更新 floor 或 ceil，并向对应方向走；命中则提前结束。
2. 走到空指针时停止。此时 floor、ceil 至少有一个存在。
3. 比较 K − floor 与 ceil − K：哪边小输出哪边；相等则两个都输出。

整条路径长度 ≤ BST 高度 h，所以时间 O(h)，空间 O(1)（只用了几个标量）。

编者注（生僻术语）：术语 floor (下界) 指 BST 中 ≤ K 的最大键，ceil (上界) 指 ≥ K 的最小键。这两个名字出自数学里的「向下取整 / 向上取整」，在 BST / 有序集合面试题中是高频概念，记住它能省下很多解释。

(2) 代码实现 [8 分]

typedef struct BSTNode {
    int data;
    struct BSTNode *left, *right;
} BSTNode;

// 找出 BST 中与 K 之差绝对值最小的所有关键字并打印
// 输出形式：第一行为最小 |差|，第二行升序输出对应关键字
void closestKey(BSTNode *T, int K) {
    int hasFloor = 0, hasCeil = 0;     // floor / ceil 是否已经找到
    int floorV = 0,  ceilV = 0;        // 当前最佳的 floor / ceil 值
    BSTNode *cur = T;

    while (cur != NULL) {
        if (cur->data == K) {                 // 命中：差为 0，唯一答案就是 K
            printf("0\n%d\n", K);
            return;
        } else if (cur->data < K) {
            // cur 比 K 小，是更优的 floor 候选；右子树里可能还有更接近 K 的下界
            if (!hasFloor || cur->data > floorV) {
                hasFloor = 1;
                floorV = cur->data;
            }
            cur = cur->right;
        } else {                              // cur->data > K
            if (!hasCeil || cur->data < ceilV) {
                hasCeil  = 1;
                ceilV    = cur->data;
            }
            cur = cur->left;
        }
    }

    // 路径走完，根据 floor / ceil 是否存在以及谁更近输出结果
    if (!hasFloor) {                                          // 整棵树都比 K 大
        printf("%d\n%d\n", ceilV - K, ceilV);
    } else if (!hasCeil) {                                    // 整棵树都比 K 小
        printf("%d\n%d\n", K - floorV, floorV);
    } else {
        int df = K - floorV, dc = ceilV - K;
        if (df < dc)      printf("%d\n%d\n", df, floorV);
        else if (dc < df) printf("%d\n%d\n", dc, ceilV);
        else              printf("%d\n%d %d\n", df, floorV, ceilV);  // 并列双解，升序
    }
}

关键点说明：

• 沿一条路径下降，绝不递归整棵树。考研学生最容易写错的版本是「中序遍历整棵树挨个比较」——那是 O(n)，完全没用上 BST 的性质，会丢分。本题的得分点就是「O(h)」。
• floor/ceil 各更新一次就够吗？够。沿路径走时，每转向右就保证 floor 在变大、每转向左就保证 ceil 在变小，所以走到底时 floor 是路径上 ≤ K 的最大者、ceil 是路径上 ≥ K 的最小者；又因为 BST 性质保证「不在路径上的结点不可能比路径上的结点更接近 K」，floor/ceil 即为全局最优。
• 并列输出顺序：题目说「所有结点」，并列时 floor < K < ceil，所以 floorV ceilV 自然就是升序，无需额外排序。
• 复杂度：时间 O(h)，h 为树高（平均 O(log n)，最坏退化成单链时 O(n)）；空间 O(1)，只用了几个标量。如果用递归写，则会多 O(h) 的栈空间，本题用迭代更优。