自助建站免费平台做百度收录的网站

自助建站免费平台,做百度收录的网站,域名注册空间网站,营销网站更受用户欢迎的原因是目录 一、方法一#xff1a;递归边界约束法#xff08;范围校验#xff09; 1. 核心思想 2. 完整实现代码 3. 重点 难点 二、方法二#xff1a;中序遍历法#xff08;利用 BST 特性#xff09; 1. 核心思想 2. 实现代码 版本 1#xff1a;递归中序遍历递归边界约束法范围校验1. 核心思想2. 完整实现代码3. 重点 难点二、方法二中序遍历法利用 BST 特性1. 核心思想2. 实现代码版本 1递归中序遍历简洁易理解版本 2迭代中序遍历避免递归栈溢出3. 重点 难点三、两种方法对比四、常见易错点总结五、总结验证二叉搜索树BST是二叉树高频面试题核心考点是准确理解 BST 的定义左子树所有节点值 根节点值右子树所有节点值 根节点值且左右子树也必须是 BST而非仅 “根节点大于左孩子、小于右孩子”。以下总结两种主流解法涵盖核心思想、实现、重点难点及对比。一、方法一递归边界约束法范围校验1. 核心思想基于 BST 的定义为每个节点划定合法取值范围左边界 节点值 右边界根节点的初始范围是(Long.MIN_VALUE, Long.MAX_VALUE)用 Long 避免 int 极值溢出递归遍历左子树时更新右边界为当前节点值左子树所有节点必须 当前节点递归遍历右子树时更新左边界为当前节点值右子树所有节点必须 当前节点若所有节点都满足范围约束则为合法 BST。2. 完整实现代码class Solution { // 递归函数校验当前节点是否在(left, right)范围内且子树满足BST private boolean isValidBSTHelper(TreeNode root, long left, long right) { if (root null) return true; // 空树是合法BST long curVal root.val; // 核心当前节点超出范围 → 不合法递归校验左右子树 if (curVal left || curVal right) return false; return isValidBSTHelper(root.left, left, curVal) // 左子树范围(left, curVal) isValidBSTHelper(root.right, curVal, right); // 右子树范围(curVal, right) } public boolean isValidBST(TreeNode root) { // 初始范围用Long极值避免int最大值/最小值的溢出问题 return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE); } }注个人暂时感觉这个思路好理解一点很多方法其实只需要记一种然后面试的时候思路清晰就OK3. 重点 难点重点范围约束需覆盖 “子树所有节点”而非仅直接子节点用Long类型替代int作为边界解决Integer.MAX_VALUE/Integer.MIN_VALUE作为节点值时的校验失效问题如测试用例[2147483647]。难点容易误将边界设为Integer极值导致极端值校验失败递归时边界更新方向易混淆左子树更新右边界右子树更新左边界。二、方法二中序遍历法利用 BST 特性1. 核心思想BST 的核心特性中序遍历结果是严格递增的序列左→根→右值从小到大。遍历过程中记录前一个节点的值若当前节点值 ≤ 前一个节点值说明不满足递增特性不是合法 BST遍历完成后未发现违规则为合法 BST。2. 实现代码版本 1递归中序遍历简洁易理解class Solution { private long preVal Long.MIN_VALUE; // 记录前一个节点值初始为Long最小值 public boolean isValidBST(TreeNode root) { // 中序遍历左→根→右 if (root null) return true; // 先遍历左子树左子树不合法直接返回false if (!isValidBST(root.left)) return false; // 校验当前节点若≤前一个值不合法 if (root.val preVal) return false; // 更新前一个节点值为当前值注意此处应该递归到了最底层从左子树最下面的节点开始的 preVal root.val; // 遍历右子树 return isValidBST(root.right); } }版本 2迭代中序遍历避免递归栈溢出class Solution { public boolean isValidBST(TreeNode root) { if (root null) return true; DequeTreeNode stack new LinkedList(); long preVal Long.MIN_VALUE; TreeNode cur root; // 迭代中序遍历模板 while (cur ! null || !stack.isEmpty()) { // 先遍历左子树全部入栈 while (cur ! null) { stack.push(cur); cur cur.left; } // 弹出栈顶当前最左节点 cur stack.pop(); // 校验递增性 if (cur.val preVal) return false; preVal cur.val; // 遍历右子树 cur cur.right; } return true; } }3. 重点 难点重点利用 BST 中序递增的特性将 “验证 BST” 转化为 “验证序列递增”逻辑更直观初始preVal需设为Long.MIN_VALUE避免节点值为Integer.MIN_VALUE时误判。难点递归版需注意preVal的作用域需设为成员变量 / 数组传递避免递归栈覆盖迭代版需熟练掌握中序遍历的栈实现逻辑避免节点遍历顺序错误。三、两种方法对比方法时间复杂度空间复杂度核心优势适用场景递归边界约束法O(n)O(h)直接贴合 BST 定义逻辑严谨需快速验证、递归深度可控中序遍历法递归O(n)O(h)利用 BST 特性代码简洁面试中快速手写、逻辑直观中序遍历法迭代O(n)O(h)避免递归栈溢出处理深度极大的二叉树注n 为节点数h 为树的高度平衡树 hlogn斜树 hn四、常见易错点总结边界类型错误用int而非Long作为边界 / 前值导致Integer.MAX_VALUE/Integer.MIN_VALUE测试用例失效BST 定义理解偏差仅校验 “根 左孩子、根 右孩子”未约束整个子树的范围如[5,1,4,null,null,3,6]会误判为合法中序遍历递增性错误将 “严格递增” 写成 “非递减”BST 不允许节点值相等递归边界更新错误左子树更新左边界、右子树更新右边界正确应为左子树更右边界右子树更左边界。五、总结递归边界法是 “从定义出发” 的通用解法需重点掌握范围约束和类型溢出问题中序遍历法是 “利用特性的巧解”核心是记住 BST 中序递增的关键性质面试中优先选择中序遍历代码简洁若面试官追问 “避免递归栈溢出”可补充迭代版若追问 “BST 定义的严格实现”可补充递归边界法。