二叉搜索树如何处理重复值？面试中比较边界应该怎么说清楚？

简化版

BST 是否允许重复值不是唯一标准，必须先约定规则：重复值放左、放右，或在节点上维护计数 count。不同规则会影响验证、插入、删除、中序遍历和区间查询的比较符，面试中要先说清楚再写代码。

详细版

常见处理方式有三种：

不允许重复值：左子树 < root，右子树 > root；
重复值固定放一侧：如左子树 <= root，右子树 > root；
节点维护 count：树中每个值只存一个节点，重复出现时 count++。

选择不同，代码边界不同。例如验证 BST 时：

不允许重复：用开区间 (low, high)；
重复放左：左侧允许 <= root，右侧必须 > root；
计数方式：结构仍按严格 BST 验证，重复由 count 表示。

面试回答 BST 题时，如果题目没有说明重复值，应主动说「默认不允许重复；若允许，需要约定重复值归属」。

完整版教学

一、为什么重复值是 BST 题的隐形坑

很多 BST 题默认使用严格定义：左子树所有值小于根，右子树所有值大于根。但现实数据经常有重复值，比如分数、时间戳、订单金额。重复值一出现，< 和 <= 的选择就不再是小细节，而会直接影响树结构和算法正确性。

比如验证 BST 时，如果你写 low < val < high，就不允许重复；如果题目允许重复放右边，那么右子树的下界可能允许等于根。题目不说清楚时，最好先声明假设，避免面试官用重复值反例卡你。

记忆钩子：BST 的重复值不是语法问题，是「全树不变量」问题；比较符一变，所有相关算法都要跟着变。

二、三种常见设计方案

重复值通常有三种处理方式。第一种是不允许重复，这是算法题最常见假设。第二种是重复值固定放左边或右边，这样中序仍然是非降序。第三种是在节点里增加 count 字段，相同值只占一个结构节点。

方案	树结构规则	优点	缺点
不允许重复	左 `<` 根 `<` 右	定义简单	不能表示重复数据
重复固定放一侧	如左 `<=` 根 `<` 右	插入逻辑直观	树可能因重复值退化
节点计数 count	结构严格，节点记录次数	删除和统计高效	节点结构更复杂

工程上如果重复值很多，count 方式更常见，因为一万个相同值不会形成一条长链。

三、重复值会怎样影响插入

不允许重复时，插入遇到相等值可以拒绝、覆盖或返回已有节点。重复放右时，遇到相等就继续往右；重复放左则继续往左。计数方式则是遇到相等就 count++，不再创建新节点。

TreeNode insert(TreeNode root, int x) {
    if (root == null) return new TreeNode(x);
    if (x < root.val) root.left = insert(root.left, x);
    else if (x > root.val) root.right = insert(root.right, x);
    else root.count++; // 计数方案
    return root;
}

如果采用重复固定放右，上面的 else root.count++ 就要改成 root.right = insert(root.right, x)。这不是实现偏好，而是数据结构定义的一部分。

四、重复值会怎样影响验证 BST

验证 BST 最怕局部判断。不能只检查 node.left.val <= node.val <= node.right.val，必须用全局上下界。重复值规则会影响上下界开闭。

严格 BST:      low < val < high
重复放左:      low < val <= high（左子树高界可等于根）
重复放右:      low <= val < high（右子树低界可等于根）
计数方案:      结构仍用 low < val < high

这个表只是表达思路，实际代码里用开闭区间很容易写乱，面试时可以先说明规则，再用递归参数表达「是否允许等于边界」。如果题目默认 LeetCode 风格，通常使用严格 BST。

五、重复值会怎样影响删除

计数方案删除最方便：如果 count > 1，只需要 count--，不用改变树结构；只有 count == 1 时才执行普通 BST 删除。重复固定放一侧时，相同值可能分散成一条链，删除某一个值就和普通节点删除一样，需要处理 0、1、2 个子节点。

带数字例子：插入 [5,5,5,5]。重复放右会形成高度 4 的右链；计数方案只有一个值为 5 的节点，count=4。如果删除一次，前者要删除链上某个节点，后者只是 count=3。

六、重复值对中序和区间查询的影响

只要重复值规则保持一致，中序遍历仍应是非降序序列。若用 count，输出所有元素时要把同一个值输出 count 次；若只输出不同值，就输出一次并附带 count。区间查询时，边界等于 low 或 high 的重复值是否全部包含，也要根据题目要求处理。

任务	重复值处理重点
中序输出所有元素	count 方案要重复输出 count 次
求众数	count 可直接参与频次
区间查询	边界值重复要全部保留
第 K 小	count 方案要把一个节点贡献 count 个排名

这说明重复值不是某一道题的局部问题，而会贯穿 BST 的所有操作。

七、常见误区与追问

误区：BST 默认一定能随便放重复值。 重复值必须有统一规则，否则查找和验证会不确定。
追问：为什么计数方案适合大量重复值？ 它避免相同值形成长链，插入和删除更稳定。
误区：把 < 改成 <= 就万事大吉。 验证、插入、删除、区间查询的边界都要同步修改。
追问：中序遍历遇到重复值还一定有序吗？ 只要规则一致，它是非降序，而不是严格升序。
误区：验证 BST 只看父子节点即可。 重复值场景更需要全局上下界，否则深层越界会漏判。

八、加强记忆

BST 重复值要先问「规则是什么」。不允许重复最简单；重复固定放一侧实现直观但可能退化；节点维护 count 更适合重复很多的数据。规则一旦确定，比较符、验证区间、删除逻辑、中序输出和第 K 小排名都要跟着统一。面试里主动声明假设，是防止边界争议的最好办法。

简化版

详细版