目录题目要求思路一:模拟迭代Javac++思路二:递归JavaC++Rust题目要求 思路一:模拟迭代 依次判断每个节点是否合法:首先找出结果的根,若原根小了就拉右边的过来,大了
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;
}
}
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;
}
};
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;
}
}
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;
}
};
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
}
}
以上就是Java C++ 算法题解LeetCode669修剪二叉搜索树的详细内容,更多关于Java C++ 算法修剪二叉搜索树的资料请关注编程网其它相关文章!
--结束END--
本文标题: Java C++ 算法题解leetcode669修剪二叉搜索树示例
本文链接: https://www.lsjlt.com/news/167476.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0