Java C++ 算法题解leetcode669修剪二叉搜索树示例
作者:AnjaVon 时间:2022-09-22 04:56:13
题目要求
思路一:模拟迭代
依次判断每个节点是否合法:
左子树判断是否>low,合法就向左下走,不合法往右下;
右子树判断是否<high,合法就向右下走,不合法往左下。
首先找出结果的根,若原根小了就拉右边的过来,大了拉左边的过来做新根;
然后分别判断左右子树的大小,由于二叉搜索树的性质,子树只需要判断一边就好:
Java
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
while (root != null && (root.val < low || root.val > high)) // 确定原根是否合法
root = root.val < low ? root.right : root.left;
TreeNode res = root;
while (root != null) {
while (root.left != null && root.left.val < low)
root.left = root.left.right;
root = root.left;
}
root = res;
while (root != null) {
while (root.right != null && root.right.val > high)
root.right = root.right.left;
root = root.right;
}
return res;
}
}
时间复杂度:O(n)
空间复杂度:O(1)
C++
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
while (root != nullptr && (root->val < low || root->val > high)) // 确定原根是否合法
root = root->val < low ? root->right : root->left;
TreeNode* res = root;
while (root != nullptr) {
while (root->left != nullptr && root->left->val < low)
root->left = root->left->right;
root = root->left;
}
root = res;
while (root != nullptr) {
while (root->right != nullptr && root->right->val > high)
root->right = root->right->left;
root = root->right;
}
return res;
}
};
时间复杂度:O(n)
空间复杂度:O(1)
思路二:递归
直接用当前函数递归修剪即可:
当前值小了放右下(大)的值进去,剪掉当前和左边节点;
当前值大了放左下(小)的值进去,剪掉当前和右边节点。
然后递归掉下面所有节点。
Java
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null)
return null;
if (root.val < low)
return trimBST(root.right, low, high);
else if (root.val > high)
return trimBST(root.left, low, high);
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
时间复杂度:O(n)
空间复杂度:O(1),忽略递归的额外空间开销
C++
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr)
return nullptr;
if (root->val < low)
return trimBST(root->right, low, high);
else if (root->val > high)
return trimBST(root->left, low, high);
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
时间复杂度:O(n)
空间复杂度:O(1),忽略递归的额外空间开销
Rust
今天又见识到了新报错:
already borrowed: BorrowMutError
,不能把borrow
的东西来回随便等,要搞临时中间变量,闭包要关好。
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn trim_bst(root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32) -> Option<Rc<RefCell<TreeNode>>> {
if root.is_none() {
return None;
}
if root.as_ref().unwrap().borrow().val < low {
return Solution::trim_bst(root.as_ref().unwrap().borrow().right.clone(), low, high);
}
else if root.as_ref().unwrap().borrow().val > high {
return Solution::trim_bst(root.as_ref().unwrap().borrow().left.clone(), low, high);
}
let (l, r) = (Solution::trim_bst(root.as_ref().unwrap().borrow().left.clone(), low, high), Solution::trim_bst(root.as_ref().unwrap().borrow().right.clone(), low, high)); // 要先拎出来
root.as_ref().unwrap().borrow_mut().left = l;
root.as_ref().unwrap().borrow_mut().right = r;
root
}
}
时间复杂度:O(n)
空间复杂度:O(1),忽略递归的额外空间开销
来源:https://juejin.cn/post/7141754690194112542
标签:Java,C++,修剪,二叉搜索树,算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
SpringBoot打成war包在tomcat或wildfly下运行的方法
2023-11-23 08:20:56
Java KindEditor粘贴图片自动上传到服务器功能实现
2023-08-07 01:42:33
![](https://img.aspxhome.com/file/2023/2/57902_0s.gif)
tk.Mybatis 插入数据获取Id问题
2023-07-01 22:03:13
![](https://img.aspxhome.com/file/2023/6/60826_0s.png)
Java 设计模式中的策略模式详情
2023-08-06 03:45:11
![](https://img.aspxhome.com/file/2023/1/57731_0s.png)
Scala中的mkString的具体使用方法
2023-11-16 00:18:18
Java真题实练掌握哈希表的使用
2023-11-09 06:33:15
![](https://img.aspxhome.com/file/2023/9/59079_0s.png)
MyBatis-Plus联表查询以及分页代码实例
2023-11-26 01:51:32
![](https://img.aspxhome.com/file/2023/8/60028_0s.png)
使用Spring Security OAuth2实现单点登录
2023-08-13 01:44:34
Spring Cloud Gateway(读取、修改 Request Body)的操作
2023-11-09 19:25:46
![](https://img.aspxhome.com/file/2023/0/59240_0s.jpg)
Android Studio 引用外部依赖时报错的解决方法
2023-09-26 18:20:11
Android编程开发之TextView单击链接弹出Activity的方法
2023-08-06 18:27:11
![](https://img.aspxhome.com/file/2023/4/83544_0s.png)
关于Java中的IO流总结(推荐)
2023-08-23 18:13:56
![](https://img.aspxhome.com/file/2023/1/58191_0s.jpg)
java 动态生成bean的案例
2023-08-09 02:20:05
SpringBoot如何通过Feign调用传递Header中参数
2023-11-24 21:39:29
Spring超详细讲解创建BeanDefinition流程
2023-11-25 08:37:55
![](https://img.aspxhome.com/file/2023/0/59940_0s.png)
解决Spring Cloud feign GET请求无法用实体传参的问题
2023-11-17 14:14:05
Java中方法的使用、重载与递归的详细介绍
2022-03-02 02:50:05
![](https://img.aspxhome.com/file/2023/8/60928_0s.png)
eclipse实现ElGamal数字签名
2023-11-26 07:52:47
基于Flutter实现图片选择和图片上传
2023-07-06 04:28:50
![](https://img.aspxhome.com/file/2023/1/106021_0s.jpg)
解析JAVA深度克隆与浅度克隆的区别详解
2023-11-02 10:57:28