【寸铁的刷题笔记】树、dfs、bfs、回溯、递归(三)
【寸铁的刷题笔记】树、dfs、bfs、回溯、递归(三)
大家好 我是寸铁👊
金三银四，树、dfs、bfs、回溯、递归是必考的知识点✨
快跟着寸铁刷起来！面试顺利上岸👋
喜欢的小伙伴可以点点关注 💝
530. 二叉搜索树的最小绝对差
考点
DFS、双指针
思路
思路：双指针,一个指针用于记录当前的节点(回溯时的当前节点),一个指针用于记录上一个节点。
不断更新两个指针的值的差值的最小值即可
代码
/**
* 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 {
/*
思路：双指针,一个指针用于记录当前的节点(回溯时的当前节点),一个指针用于记录上一个节点。
不断更新两个指针的值的差值的最小值即可
*/
TreeNode pre; //记录上一个遍历的节点
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root == null)return 0;
traversal(root);
return result;
}
public void traversal(TreeNode root){
if(root == null)return; // 遍历到最后一个节点时,终止,向上回溯
//左
traversal(root.left);
//中
if(pre != null){
result = Math.min(result , root.val - pre.val);
}
//一开始时,pre为空节点,递归到最后一个节点时,记录当前的节点
//向上回溯时,pre为上一个节点,root为此时的节点,做差即可
//当pre不为空时,再进行做差取最小值操作。
pre = root;
//右
traversal(root.right);
}
}
230. 二叉搜索树中第K小的元素
考点
DFS、回溯
思路
思路：二叉搜索树的中序遍历是有序数组,顺序为：
从小到大
左<中<右,根据这一点,先遍历左子树,判断遍历到的节点的数量cnt是否等于k
如果cnt等于k,则说明这个节点就是第k个节点。
代码
class Solution {
int res = -1;//记录第K个数的节点值
int cnt = 0; //记录当前遍历到的节点个数
/*
思路：二叉搜索树的中序遍历是有序数组,顺序为：从小到大
左<中<右,根据这一点,先遍历左子树,判断遍历到的节点的数量是否等于k
如果等于,则说明这个节点就是第k个节点。
*/
public int kthSmallest(TreeNode root, int k) {
dfs(root , k);
return res;//res全局变量,直接返回res即可。
}
public void dfs(TreeNode root, int k){
if(root == null)return;//直接结束
//左子树
dfs(root.left , k);
//注意:这里是第k个 从1开始,cnt要先++
if(++cnt == k){
res = root.val;
return;
//一种理解是函数直接结束
//一种理解是向上回溯,把结果返回给根节点。
}
//右子树
dfs(root.right , k);
}
}
98. 验证二叉搜索树
考点
DFS、双指针、回溯
与 530. 二叉搜索树的最小绝对差的处理逻辑类似
思路
思想:根据定义,节点的左子树
小于当前节点,节点的右子树大于当前节点
也就是left < middle < right
很自然的就想到了用中序遍历,再判断一下是否满足left < middle < right即可
进一步,我们只需要判断当前的节点是否小于之前的节点。
如果小于则不满足条件,向上返回false即可。
否则，则满足条件。
代码
class Solution {
/*
思想:根据定义,节点的左子树小于当前节点,节点的右子树大于当前节点
也就是left < middle < right
很自然的就想到了用中序遍历,再判断一下是否满足left < middle < right即可
进一步,我们只需要判断当前的节点是否小于之前的节点。
如果小于则不满足条件,向上返回false即可。
否则，则满足条件。
*/
TreeNode pre; //存储上一个节点
public boolean isValidBST(TreeNode root) {
//如果节点为空则直接返回true
if(root == null)return true;
//左 创建一个变量记录左子树递归的结果
boolean left = isValidBST(root.left);
if(!left){
return false;
}
//中 处理条件的逻辑 判断当前节点是否 <= 上一个节点
if(pre != null && root.val <= pre.val){
return false;
}
//一开始为空,记录上一个节点。
pre = root;
//右 创建一个变量记录右子树递归的结果
boolean right = isValidBST(root.right);
//向上返回右子树递归的结果 right
// if(!right){
// return false;
// }
//与下等效,考虑到方法的返回语句,如下编译通过。
return right;
}
}
看到这里的小伙伴，恭喜你又掌握了一个技能👊
希望大家能取得胜利，坚持就是胜利💪
我是寸铁！我们下期再见💕
往期好文💕
保姆级教程
【保姆级教程】Windows11下go-zero的etcd安装与初步使用
【保姆级教程】Windows11安装go-zero代码生成工具goctl、protoc、go-zero
【Go-Zero】手把手带你在goland中创建api文件并设置高亮
报错解决
【Go-Zero】Error: user.api 27:9 syntax error: expected ‘:‘ | ‘IDENT‘ | ‘INT‘, got ‘(‘ 报错解决方案及api路由注意事项
【Go-Zero】Error: only one service expected goctl一键转换生成rpc服务错误解决方案
【Go-Zero】【error】 failed to initialize database, got error Error 1045 (28000):报错解决方案
【Go-Zero】Error 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: YES)报错解决方案
【Go-Zero】type mismatch for field “Auth.AccessSecret“, expect “string“, actual “number“报错解决方案
【Go-Zero】Error: user.api 30:2 syntax error: expected ‘)‘ | ‘KEY‘, got ‘IDENT‘报错解决方案
【Go-Zero】Windows启动rpc服务报错panic:context deadline exceeded解决方案
Go面试向
原文地址：https://blog.csdn.net/joeyoj/article/details/136268176
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！