如何打印二叉树中无法用二分搜索查找的非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
相关产品推荐
相关产品推荐

