You need to enable JavaScript to run this app. 如何打印二叉树中无法用二分搜索查找的非BST结构节点并修复现有代码问题?
优惠活动
大模型
产品
解决方案
定价
更多

如何打印二叉树中无法用二分搜索查找的非BST结构节点并修复现有代码问题?

代码失效的根本原因

当前实现对BST的规则理解存在偏差,校验逻辑仅对比节点与直接父节点的大小关系,把BST的约束简化成了单相邻父子层的规则,但实际上:
BST的合法性核心是全局的子树范围约束,不是单父子节点对比即可满足的——从某祖先节点的左分支走下来的所有节点,值都必须小于该祖先节点;从某祖先节点的右分支走下来的所有节点,值都必须大于该祖先节点。
你的测试用例里,值为51的节点是根节点7的左子树分支上的节点,按照规则必须小于7。但当前代码递归到该节点时,仅校验了「51 > 直接父节点2」这个单父子关系,完全没有收到上层传递的“左子树节点必须小于7”的约束信息,自然无法识别这个跨层级的违规。

正确实现思路

递归遍历二叉树时,为每一层的递归调用传递当前子树对应的合法值上下限,逐节点校验是否落在合法区间内:

  • 遍历根节点时,合法区间为[Integer.MIN_VALUE, Integer.MAX_VALUE](模拟无边界的无穷范围)
  • 遍历当前节点的左子树时,将合法区间的右边界收紧为当前节点的值,保证左子树所有节点必须小于当前节点
  • 遍历当前节点的右子树时,将合法区间的左边界收紧为当前节点的值,保证右子树所有节点必须大于当前节点
  • 若节点值超出当前合法区间,即为无法通过二分搜索定位的违规节点,直接输出即可。
修正后的代码片段

替换原有递归校验逻辑即可,不需要改动原有的Node类结构:

// 核心递归校验:传入当前节点对应的合法值上下限
private void checkAndPrintIllegal(Node node, int minLimit, int maxLimit) {
    if (node == null) return;
    // 节点值越界即为违规,会无法通过二分搜索定位
    if (node.key <= minLimit || node.key >= maxLimit) {
        System.out.print(node.key + " ");
    }
    // 递归左子树:更新右边界为当前节点值
    checkAndPrintIllegal(node.left, minLimit, node.key);
    // 递归右子树:更新左边界为当前节点值
    checkAndPrintIllegal(node.right, node.key, maxLimit);
}

// 原入口方法适配
private void printSearchable(Node root) {
    checkAndPrintIllegal(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

用你原来的测试树测试时,遍历到值为51的节点时,递归上下文传递的合法区间是(2,7),51远大于区间上限7,会被正确识别为违规节点输出,不会出现漏判。


内容的提问来源于stack exchange,提问作者user11647698

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.20 12:24:03