【算法系列-二叉树】二叉搜索树的搜索&验证
文章目录
- 【算法系列-二叉树】二叉搜索树的搜索&验证
- 1. 算法分析🛸
- 2. 二叉搜索树中的搜索(LeetCode 700)
- 2.1 思路分析🎯
- 2.2 代码示例🌰
- 3. 验证二叉搜索树(LeetCode 98)
- 3.1 迭代
- 3.1.1 思路分析🎯
- 3.1.2 代码示例🌰
- 3.2 递归
- 3.2.1 思路分析🎯
- 3.2.2 代码示例🌰
1. 算法分析🛸
在开始写题之前,我们需要先了解二叉搜索树的特性:
- 若二叉搜索树的左子树不为空,则其左子树上所有的节点的值都小于其根节点的值;
- 若二叉搜索树的右子树不为空,则其右子树上所有的节点的值都大于其根节点的值;
- 它的左右子树也是二叉搜索树;
可以看出二叉搜索树是一个有序树,即根比左大,右比根大,很适合用中序遍历来进行操作
2. 二叉搜索树中的搜索(LeetCode 700)
【题目链接】700. 二叉搜索树中的搜索 - 力扣(LeetCode)
2.1 思路分析🎯
理解了上述二叉搜索树的特性后,这道题就简单很多了,只需要在遍历每个节点时判断它的大小即可:
当节点值大于目标值时,遍历左节点;
当节点值小于目标值时,遍历右节点;
当节点值与目标值相同时,返回当前节点即可
2.2 代码示例🌰
class Solution {public TreeNode searchBST(TreeNode root, int val) {return dfs(root, val);}TreeNode dfs(TreeNode node, int val) {if (node == null) {return null;}if (node.val == val) {return node;}return node.val < val ? dfs(node.right, val) : dfs(node.left, val);}
}
3. 验证二叉搜索树(LeetCode 98)
【题目链接】98. 验证二叉搜索树 - 力扣(LeetCode)
这道题提供两种解题思路,迭代 与 递归;
3.1 迭代
3.1.1 思路分析🎯
迭代的方式比较简单,就是基于它的特性(左节点<根节点<右节点),将所有的节点通过中序遍历的方式加入一个数组中,最后对数组进行遍历判断,若数组是按递增顺序排列的,则此二叉树为搜索树,否则非二叉搜索树;
3.1.2 代码示例🌰
class Solution {TreeNode max;public boolean isValidBST(TreeNode root) {List<Integer> list = new ArrayList<>();dfs(root, list);for (int i = 0;i < list.size();i++) {if (i + 1 < list.size()) {if (list.get(i) >= list.get(i + 1)) {return false;}}}return true;}void dfs(TreeNode node, List<Integer> list) {if (node == null) {return;}dfs(node.left, list);list.add(node.val);dfs(node.right, list);}
}
3.2 递归
3.2.1 思路分析🎯
定义一个最大值,通过中序遍历进行操作,每递归完左子树开始遍历根节点时,进行判断:
当根节点的值小于等于最大值时,表示此时的根节点小于它自己的左节点,返回false;否则将当前节点的值赋值给max;之后开始遍历右节点,若最后左右节点判断都为true,表示当前根节点的符合二叉搜索树,返回true,回到当前根节点上一个节点,重复上述过程直到所有节点都遍历完毕;
注:
这里有个坑,就是这里判断搜索树的标准,开始设置的最小值不能是一个Integer.MIN_VALUE(java中即-2147483648),这是个坑,因为在输入的参数中可能出现这个值,假设此时节点只有一个且值刚好等于
-2147483648
,那么它在结束左节点递归开时判断根节点是否大于左节点时,根节点的值与最小值相等,会返回false,这是一个错误的结果;
修改如下:
将max改为一个节点,并在判断时先判断max是否为空,则可以规避最开始时的叶子节点max未赋值的情况;
或者使用Long.MIN_VALUE(当节点值类型小于long类型时可以使用,如int)
3.2.2 代码示例🌰
使用Long.MIN_VALUE
class Solution {long max = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {return dfs(root);}boolean dfs(TreeNode cur) {if (cur == null) {return true;}boolean leftFlag = dfs(cur.left);if (cur.val <= max) {return false;}max = cur.val;boolean rightFlag = dfs(cur.right);return leftFlag && rightFlag;}
}
使用节点max:
class Solution {TreeNode max;public boolean isValidBST(TreeNode root) {return dfs(root);}boolean dfs(TreeNode cur) {if (cur == null) {return true;}boolean leftFlag = dfs(cur.left);if (max != null && cur.val <= max.val) {return false;}max = cur;boolean rightFlag = dfs(cur.right);return leftFlag && rightFlag;}
}
以上便是关于二叉搜索树问题的介绍了!!后续还会继续分享其它算法系列内容,如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨
题外话:又是一年的生日,记得上一次生日也在文章末尾作留言纪念(开始mysql章节的时候),这一年收获了很多的成长,无论是技术上的提升还是面对困难时心态的自我调整,都是自身进步的体现。新的时间点,期望收获更多的进步与成长,路在自己脚下,走好自己的路就好,加油( •̀ ω •́ )✧!!