当前位置:网站首页>Leetcode刷题——二叉搜索树相关题目(98. 验证二叉搜索树、235. 二叉搜索树的最近公共祖先、1038. 从二叉搜索树到更大和树、538. 把二叉搜索树转换为累加树)
Leetcode刷题——二叉搜索树相关题目(98. 验证二叉搜索树、235. 二叉搜索树的最近公共祖先、1038. 从二叉搜索树到更大和树、538. 把二叉搜索树转换为累加树)
2022-08-04 11:06:00 【lonelyMangoo】
概念
二叉搜索树:
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
而二叉搜索树的中序遍历时升序。
98. 验证二叉搜索树
题目:98. 验证二叉搜索树
思路:用中序遍历判断,当前节点是否大于之前一个。
//迭代写法
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack();
TreeNode cur = root;
TreeNode pre = null;
while (cur!=null || !stack.isEmpty()){
if(cur != null){
stack.add(cur);
cur = cur.left;
}
else {
cur = stack.pop();
if(pre!=null && pre.val>= cur.val){
return false;
}
//记录前一个节点
pre=cur;
cur=cur.right;
}
}
return true;
}
我一开始用的层次遍历,因为忽略了整体也要大于的情况:
也就是例子中的5、3这种情况。
当然这里也可以用递归实现,也是中序遍历并记录前一个节点
TreeNode pre=null;
public boolean isValidBST(TreeNode root) {
if(root == null ) return true;
boolean left = isValidBST(root.left);
//中序遍历操作部分
if(pre!=null && root.val <= pre.val){
return false;
}
pre = root;
boolean right =isValidBST(root.right);
return left && right;
}
我觉得递归还是比较难理解的,虽然思路是一样的但是可能不知道哪一层就出问题了,所以面试遇到还是用迭代不容易出错。
235. 二叉搜索树的最近公共祖先
题目:235. 二叉搜索树的最近公共祖先
这题只需要别人提供一个思路就能写出来:
要求的两个节点都比当前节点小,到左子树中去找
要求的两个节点都比当前节点大,到右子树中去找
如果一个比当前节点大,一个比当前节点小,就是要求的节点。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p.val<root.val && q.val<root.val){
return lowestCommonAncestor(root.left, p, q);
}
else if(p.val>root.val && q.val>root.val){
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
538. 把二叉搜索树转换为累加树
这两道题是一样的
538. 把二叉搜索树转换为累加树
1038. 从二叉搜索树到更大和树
重新建树
第一种思路是容易想到的,先中序遍历得到所有需要的值,然后再次中序遍历给树赋值。
public TreeNode bstToGst(TreeNode root) {
List<Integer> list = new ArrayList<>();
inorder(root, list);
//将list的值设置成题目需要的
for (int i = list.size() - 2; i >= 0; i--) {
list.set(i, list.get(i) + list.get(i + 1));
}
//重新赋值
build(root, list);
return root;
}
private static void build(TreeNode root, List<Integer> list) {
int i = 0;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
if (cur!=null){
cur.val = list.get(i++);
}
cur = cur.right;
}
}
}
private static void inorder(TreeNode root, List<Integer> list) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
//获得中序遍历的值
list.add(cur.val);
cur = cur.right;
}
}
}
递归
将中序遍历反过来就是由大到小,用一个sum记录累加即可。
int sum = 0;
public TreeNode bstToGst(TreeNode root) {
build(root);
return root;
}
//逆中序
private void build(TreeNode root){
if(root!=null){
build(root.right);
root.val+=sum;
sum=root.val;
build(root.left);
}
}
边栏推荐
- 强烈推荐一款优秀且通用的后台管理系统
- Events in August | 51CTO's 17th Anniversary Celebration, post a blog post to get gifts such as tea sets/notebooks/T-shirts!
- mae,mse,rmse分别利用sklearn和numpy实现
- Jina 实例秀|七夕神器!比你更懂你女友的AI口红推荐
- Heap Sort
- Difference between ArrayList and LinkedList
- 123
- BOSS 直聘回应女大学生连遭两次性骚扰:高度重视求职者安全,可通过 App 等举报
- 开源一夏|ArkUI如何自定义弹窗(eTS)
- 再次搞定 Ali 云函数计算 FC
猜你喜欢
随机推荐
【Idea系列】idea配置
ROI LTV CPA ECPM体系讲解
apache dolphin scheduler 文件dolphinscheduler-daemon.sh详解
JUC (1) threads and processes, concurrency and parallelism, thread state, locks, producers and consumers
linux下数据库初始化密码
Why are all hotel bathrooms transparent?
Jenkins User Manual (1) - Software Installation
AWS Lambda相关概念与实现思路
【励志】复盘的重要性
Learn to use the basic interface of set and map
Super Learning Method
面试蚂蚁(P7)竟被MySQL难倒,奋发图强后二次面试入职蚂蚁金服
利用pytest hook函数实现自动化测试结果推送企业微信
Jina 实例秀|基于神经搜索的网络安全威胁检测(一)
Difference between ArrayList and LinkedList
【LeetCode】701.二叉搜索树中的插入操作
什么是 DevOps?看这一篇就够了!
浅析深度学习在图像处理中的应用趋势及常见技巧
MySQL 45 讲 | 11 怎么给字符串字段加索引?
Doing Homework HDU - 1074