如何在二叉搜索树中查找 floor 和 ceil？

简化版

floor(x) 是不大于 x 的最大值，ceil(x) 是不小于 x 的最小值。查 floor 时，从根开始搜索：如果当前值等于 x，直接返回；如果当前值大于 x，去左边；如果当前值小于 x，当前节点可能是答案，记录它并去右边找更大的合法值。查 ceil 对称处理。

详细版

BST 的 floor/ceil 本质是“边搜索边记录候选”。查 floor 时，所有大于 x 的节点都不能作为答案，所以遇到 node.val > x 要向左走；遇到 node.val < x 时，它满足“不大于 x”，但右子树可能有更接近 x 的更大值，所以先记录当前节点，再去右边。ceil 则相反：遇到小于 x 的节点去右边，遇到大于 x 的节点记录候选并去左边。

这类题和“中序前驱/后继”关系很近：如果 x 正好存在，floor 和 ceil 都可以是 x；如果题目要求严格前驱/后继，则要排除等于 x 的情况。时间复杂度 O(h)，空间复杂度 O(1)。

完整版教学

一、先定义 floor 和 ceil

在有序集合里，floor(x) 表示小于等于 x 的最大元素，ceil(x) 表示大于等于 x 的最小元素。例如集合 [2, 4, 6, 9, 12]，当 x = 8 时，floor 是 6，ceil 是 9；当 x = 6 时，如果允许等于，floor 和 ceil 都是 6。

values = [2, 4, 6, 9, 12]
x = 8  -> floor = 6, ceil = 9
x = 6  -> floor = 6, ceil = 6
x = 1  -> floor = null, ceil = 2
x = 13 -> floor = 12, ceil = null

这组例子说明 floor/ceil 不一定都存在。面试时返回 null、-1 还是某个哨兵值，要看题目接口约定；讲思路时可以说“没有候选则返回空”。

二、floor 为什么遇小记录、向右逼近

查 floor 时，答案必须 <= x，并且越大越好。当前节点如果大于 x，它和它的右子树都太大，不能作为答案，只能去左边找更小值。当前节点如果小于 x，它是一个合法候选，但右子树里可能有更大的合法值，所以记录当前节点后向右走。

查 floor(8):
        6
       / \
      4   10
          /
         9

cur=6: 6 < 8，记录 floor=6，去右边
cur=10: 10 > 8，去左边
cur=9: 9 > 8，去左边为空
最终 floor=6

这就是“候选 + 逼近”的模式。不是找到第一个小于 x 的节点就结束，因为右边可能有更接近 x 的合法节点。

三、ceil 与 floor 完全对称

查 ceil 时，答案必须 >= x，并且越小越好。当前节点小于 x，当前节点和左子树都太小，去右边；当前节点大于 x，当前节点是合法候选，但左子树可能有更小的合法值，所以记录当前节点后去左边。

查询	当前值关系	是否记录当前节点	下一步
floor	`node.val < x`	记录	去右子树找更大的合法值
floor	`node.val > x`	不记录	去左子树
ceil	`node.val > x`	记录	去左子树找更小的合法值
ceil	`node.val < x`	不记录	去右子树
两者	`node.val == x`	直接返回 x	结束

这张表可以直接作为面试中的讲解框架。只要把“合法候选”和“继续逼近”说清楚，代码就很自然。

四、代码实现

可以分别写两个函数，也可以一次搜索同时维护 floor 和 ceil。面试中分开写更清楚；如果题目要求同时返回，再合并。

Integer floor(TreeNode root, int x) {
    Integer ans = null;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == x) return cur.val;
        if (cur.val < x) {
            ans = cur.val;
            cur = cur.right;
        } else {
            cur = cur.left;
        }
    }
    return ans;
}

Integer ceil(TreeNode root, int x) {
    Integer ans = null;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == x) return cur.val;
        if (cur.val > x) {
            ans = cur.val;
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    return ans;
}

如果节点值可能是负数，就不要用 -1 偷懒表示不存在，除非题目明确说节点值都是正数。更稳的接口是返回节点指针、包装类型或布尔标记加结果值。

五、和前驱后继的关系

floor/ceil 和 predecessor/successor 很像，但边界是否允许等于不同。floor(x) 允许等于 x；严格前驱要求 < x 的最大值。ceil(x) 允许等于 x；严格后继要求 > x 的最小值。

集合 [2, 4, 6, 9]
x = 6
floor(x) = 6
ceil(x) = 6
predecessor(x) = 4
successor(x) = 9

如果面试题把“找某节点的前驱/后继”和“找某值的 floor/ceil”混在一起问，一定要先确认是否允许等于。这个确认会显得你对边界很敏感。

六、常见误区与追问

记忆钩子：floor 见小先收下再向右贪，ceil 见大先收下再向左贪。

误区：找到小于 x 的节点就返回 floor。 右子树可能还有更大的合法值，必须继续逼近。
误区：floor 和前驱完全一样。 floor 允许等于 x，严格前驱不允许等于。
误区：不存在时统一返回 -1。 如果节点值可能包含 -1，会产生歧义，应按接口返回 null 或节点指针。
追问：复杂度是多少？ 每层只走一个方向，时间 O(h)，迭代空间 O(1)。
追问：退化 BST 会怎样？ 树高 h 变成 n，查询退化为 O(n)。
追问：能不能一次求出 floor 和 ceil？ 可以，在一次搜索中同时维护两个候选；小于 x 时更新 floor，大于 x 时更新 ceil。

七、加强记忆

floor/ceil 的核心是“边搜索边留候选”。floor 要找不超过 x 的最大值，所以遇到小于 x 的节点先记下来，再去右边试图找更大的合法值；ceil 要找不低于 x 的最小值，所以遇到大于 x 的节点先记下来，再去左边试图找更小的合法值。等于 x 时是否直接返回，取决于题目问的是 floor/ceil 还是严格前驱/后继；这个边界讲清楚，基本就不会翻车。

简化版

详细版