个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰来到了我们的每日刷题环节前面我们学习了很多二叉树相关的题目今天我们继续学习二叉树的另一种形式二叉搜素树。摘要本文介绍了二叉搜索树BST的基本概念、核心性质及操作。BST通过左小右大的规则组织数据使查找、插入和删除的平均时间复杂度达到O(logn)。文章对比了普通BST与红黑树的区别分析了BST可能退化为链表的问题及改进方案。通过两道LeetCode题目700.二叉搜索树中的搜索和98.验证二叉搜索树展示了BST的递归和迭代实现方法重点讲解了验证BST的中序遍历思路。最后指出BST在数据库索引、有序集合等场景的应用价值并强调保持平衡的重要性。前情提要什么是二叉搜索树二叉搜索树Binary Search Tree简称BST是一种特殊的二叉树它让数据的查找、插入和删除变得非常高效。其实我们在Java基础中学习过红黑树二叉搜索树BST和红黑树是两种不同的数据结构但红黑树是二叉搜索树的一种改进版本。普通BST按顺序插入 1,2,3,4,51 \ 2 \ 3 \ 4 \ 5→ 变成了链表查找5需要5次比较红黑树按顺序插入 1,2,3,4,5自动调整后text3B / \ 2R 5R / / 1B 4B→ 树是平衡的查找5只需要3次比较它的核心规则很简单就像一本自动排序的字典核心性质左子树中所有节点的值根节点的值右子树中所有节点的值根节点的值左右子树本身也是二叉搜索树递归定义8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13在这个例子中根节点 8左边全小于83,1,6,4,7右边全大于810,14,13节点 3左边1小于3右边6大于3节点 10右边14大于10左边没有符合核心操作与时间复杂度操作平均时间复杂度最坏情况查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)O(log n)非常快。比如有100万个节点最多只需要比较20次。O(n)当树退化成一条“链表”时发生比如按顺序插入1,2,3,4,5,6。实际应用场景数据库索引B树BST的升级版广泛用于数据库有序集合/映射C的std::map、Java的TreeMap、Go的container/redblacktree符号表编译器存储变量名和属性网络路由查找IP地址对应的路由规则缺点与改进缺点解决方案最坏情况退化为链表使用平衡二叉搜索树AVL树、红黑树不支持范围查询的高效实现B树用于数据库没有维护父节点指针的版本实现时额外维护parent指针一句话总结二叉搜索树是一种通过“左小右大”的规则组织数据的二叉树它让查找、插入、删除的平均复杂度降到O(log n)。但需要保持平衡否则会退化成链表。查找的通用思路递归法1.确定递归函数的参数和返回值递归函数的参数传入的就是根节点和要搜索的数值返回的就是以这个搜索数值所在的节点。2.确定终止条件如果root为空或者找到这个数值了就返回root节点。3.确定单层递归的逻辑因为二叉搜索树的节点是有序的所以可以有方向的去搜索。如果root-val val搜索左子树如果root-val val就搜索右子树最后如果都没有搜索到就返回NULL。写递归函数的时候 习惯直接写searchBST(root-left, val)却忘了 递归函数还有返回值。4.递归函数的返回值是什么左子树如果搜索到了val要将该节点返回。 如果不用一个变量将其接住那么返回值不就没了。所以要result searchBST(root-left, val)。迭代法一提到二叉树遍历的迭代法可能立刻想起使用栈来模拟深度遍历使用队列来模拟广度遍历。对于二叉搜索树可就不一样了因为二叉搜索树的特殊性也就是节点的有序性可以不使用辅助栈或者队列就可以写出迭代法。对于一般二叉树递归过程中还有回溯的过程例如走一个左方向的分支走到头了那么要调头在走右分支。而对于二叉搜索树不需要回溯的过程因为节点的有序性就帮我们确定了搜索的方向。例如要搜索元素为3的节点我们不需要搜索其他节点也不需要做回溯查找的路径已经规划好了。中间节点如果大于3就向左走如果小于3就向右走如图所以递迭代方法的代码实现起来很简单题目实战700.二叉搜索树中的搜索题目背景给定二叉搜索树BST的根节点root和一个整数值val。你需要在 BST 中找到节点值等于val的节点。 返回以该节点为根的子树。 如果节点不存在则返回null。示例 1:输入root [4,2,7,1,3], val 2输出[2,1,3]示例 2:输入root [4,2,7,1,3], val 5输出[]提示树中节点数在[1, 5000]范围内1 Node.val 107root是二叉搜索树1 val 107题目分析这道题目就是简单的二叉搜索树的查找我们直接依照上面讲解的两种方法给出实现。题目答案递归法/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public TreeNode searchBST(TreeNode root, int val) { if (root null || root.val val) { return root; } if (val root.val) { return searchBST(root.left, val); } else { return searchBST(root.right, val); } } }迭代法/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public TreeNode searchBST(TreeNode root, int val) { while (root ! null) if (val root.val) root root.left; else if (val root.val) root root.right; else return root; return null; } }98.验证二叉搜索树题目背景给你一个二叉树的根节点root判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下节点的左子树只包含严格小于当前节点的数。节点的右子树只包含严格大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1输入root [2,1,3]输出true示例 2输入root [5,1,4,null,null,3,6]输出false解释根节点的值是 5 但是右子节点的值是 4 。提示树中节点数目范围在[1, 104]内题目解析这道题目就是逆着实现的而已上一道我们是利用这个性质去查找题目给的已经是二叉搜索树而这一道题目是要根据已知的性质去判断这个树是不是二叉搜索树总之还是利用这个性质。但是实现起来还是有点小坑的我们怎么用代码去判断这个树是不是二叉搜索树呢如果给我们用眼睛去看我们肯定都能判断出来根节点的左边都是小右边都是大。但是代码该怎么去写有一个思路就是利用这个大小关系我们利用中序遍历把二叉树转成一个集合数组需要知道大小集合可以自动扩容然后判断数组的是否是递增的中序遍历是左中右的遍历顺序也就是从小到大的顺序代码实现5/ \1 4/ \3 6第一步创建ArrayList空的javaListInteger list new ArrayList(); // list []第二步调用inorder(root, list)开始中序遍历中序遍历顺序左子树 → 根 → 右子树2.1 从根节点5开始进入inorder(5)调用inorder(5.left)→ 进入节点1进入inorder(1)调用inorder(1.left)→null返回执行list.add(1.val)→list [1]调用inorder(1.right)→null返回返回上一层节点5回到inorder(5)2.执行list.add(5.val)→list [1, 5]3. 调用inorder(5.right)→ 进入节点4进入inorder(4)调用inorder(4.left)→ 进入节点3进入inorder(3)调用inorder(3.left)→null返回执行list.add(3.val)→list [1, 5, 3]调用inorder(3.right)→null返回返回上一层节点4回到inorder(4)2.执行list.add(4.val)→list [1, 5, 3, 4]3. 调用inorder(4.right)→ 进入节点6进入inorder(6)调用inorder(6.left)→null返回执行list.add(6.val)→list [1, 5, 3, 4, 6]调用inorder(6.right)→null返回返回上一层节点4回到inorder(4)结束返回回到inorder(5)结束题目答案法一class Solution { public boolean isValidBST(TreeNode root) { ListInteger list new ArrayList(); inorder(root, list); for (int i 1; i list.size(); i) { if (list.get(i) list.get(i - 1)) return false; } return true; } private void inorder(TreeNode node, ListInteger list) { if (node null) return; inorder(node.left, list); list.add(node.val); inorder(node.right, list); } }我们也可以边遍历边比较不需要额外的空间进行存储法二过程分析使用同样的示例树非BSTtext5 / \ 1 4 / \ 3 6初始状态pre null 调用 inorder(5)第1层inorder(5)被调用text进入 inorder(5): pre null 1. 调用 inorder(5.left) → 进入节点 1第2层inorder(1)被调用text进入 inorder(1): 1. 调用 inorder(1.left) → null返回 true 2. 处理当前节点 1: - pre ! null? 否pre还是null跳过检查 - pre 1 更新前驱节点为1 3. 调用 inorder(1.right) → null返回 true 4. inorder(1) 返回 true此时状态textpre 1 list想象中的中序序列[1]回到第1层inorder(5)继续执行text回到 inorder(5): 2. 处理当前节点 5: - pre ! null? 是pre1 - 检查5 1? 否5 1通过 ✅ - pre 5 更新前驱节点为5 3. 调用 inorder(5.right) → 进入节点 4此时状态textpre 5 想象中的中序序列[1, 5]第2层inorder(4)被调用text进入 inorder(4): 1. 调用 inorder(4.left) → 进入节点 3第3层inorder(3)被调用text进入 inorder(3): 1. 调用 inorder(3.left) → null返回 true 2. 处理当前节点 3: - pre ! null? 是pre5 - 检查3 5? 是3小于5 → ❌ 返回 false这里发现违规节点3在根节点5的右子树中却比5小。回溯过程textinorder(3) 返回 false ↓ inorder(4) 收到 false立即返回 false不再继续执行 ↓ inorder(5) 收到 false立即返回 false ↓ 最终结果false核心理解1. 为什么空节点返回true因为空树是合法的二叉搜索树。二叉搜索树的定义中没有对空树做出禁止。一棵空树既没有违反左根右的规则也没有任何节点所以它天然就是合法的BST。2. 返回true的意义当遇到null时返回true意味着“这个空子树没有问题可以继续检查其他部分。”这保证了递归能正常结束不会无限递归下去。 状态变化表步骤当前节点操作pre前驱比较结果状态11左子树null处理节点1null → 1无比较prenull✅25处理节点51 → 55 1✅33处理节点353 5?否❌失败4-逐层返回false--结束class Solution { private TreeNode pre; // 记录上一个遍历的节点 public boolean isValidBST(TreeNode root) { pre null; return inorder(root); } private boolean inorder(TreeNode node) { if (node null) return true; // 左子树 if (!inorder(node.left)) return false; // 当前节点必须大于前一个节点 if (pre ! null node.val pre.val) return false; pre node; // 右子树 return inorder(node.right); } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
