html个人主页web作业_商务网页设计与制作 百度百科_汉中seo培训_百度今日数据统计

【算法系列-二叉树】二叉搜索树的搜索&验证

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章节的时候)，这一年收获了很多的成长，无论是技术上的提升还是面对困难时心态的自我调整，都是自身进步的体现。新的时间点，期望收获更多的进步与成长，路在自己脚下，走好自己的路就好，加油( •̀ ω •́ )✧！！