title: 二叉搜索树的插入删除修剪
📃 题目一描述
题目链接：701. 二叉搜索树中的插入操作
🔔 解题思路
递归法：
明确BST插入可以不用改变树的结构，所以找到对应的子节点插入即可；
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
if (val > root->val) root->right = insertIntoBST(root->right, val);
if (val < root->val) root->left = insertIntoBST(root->left, val);
return root;
}
};
迭代法：
找到叶子节点，但是是迭代的，无法像递归一样利用函数调用的栈，但是可以采用pre 来记录上一个的节点！
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
TreeNode* cur = root;
TreeNode* pre = nullptr;
while (cur) {
pre = cur;
if (cur->val > val) {
cur = cur->left;
}
else if (cur->val < val) {
cur = cur->right;
}
}
if (pre && pre->val > val) pre->left = new TreeNode(val);
else if (pre && pre->val < val) pre->right = new TreeNode(val);
else root = new TreeNode(val);
return root;
}
};
💥 复杂度分析
- 时间复杂度：O(n);
- 空间复杂度：O(1);
📃 题目二描述
题目链接：450. 删除二叉搜索树中的节点
🔔 解题思路
找到删除节点要观察：
情况一：要删除的节点是叶子节点，直接删除即可；
情况二：要删除的节点是只存有一边子树，直接删除用子树的第一个节点替上来就可；
情况三：要删除的节点存在左右两边子树，那么删除可以有多种选择方案，这里提两种
- 方案①：用删除节点的右子树第一个节点替代，如图：
- 方案②用删除节点的右子树最小值来替代，如上图，用4代替7；
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return nullptr; // 处理找不到的情况；
if (root->val == key) {
// 处理情况一、二
if (root->left == nullptr) {
TreeNode* cur = root->right;
delete root;
return cur;
}
if (root->right == nullptr) {
TreeNode* cur = root->left;
delete root;
return cur;
}
// 情况三
if (root->left && root->right) {
TreeNode* node = root->right;
while (node->left) node = node->left; // 拿到右子树最小的值；
// 方案①:将右子节点替上去；
node->left = root->left;
TreeNode* cur = root->right;
delete root;
return cur;
//方案②：将右子树中的最小值替上去；
node = new TreeNode(node->val);
root->right = deleteNode(root->right, node->val);
node->left = root->left; node->right = root->right;
delete root;
return node;
}
}
// 找左右子树
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
}
};
迭代法：
class Solution {
public:
TreeNode* deleteoOne(TreeNode* root) {
// 情况一、二
if (root->right == nullptr) return root->left;
if (root->left == nullptr) return root->right;
// 情况三，采用方案①
TreeNode* cur = root->right;
while (cur->left) cur = cur->left;
cur->left = root->left;
return root->right;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return nullptr;
TreeNode* pre = nullptr;
TreeNode* cur = root;
while (cur) {
if (cur->val == key) break;
pre = cur;
if (cur->val > key) cur = cur->left;
else cur =cur->right;
}
// 如果要删除的是头节点
if (pre == nullptr) return deleteoOne(cur);
// 如果要删除的是pre左孩子节点
if (pre->left && pre->left == cur) pre->left = deleteoOne(cur);
// 如果要删除的是pre右孩子节点
if (pre->right && pre->right == cur) pre->right = deleteoOne(cur);
return root;
}
};
💥 复杂度分析
- 时间复杂度：O(n);
- 空间复杂度：O(1);
📃 题目三描述
题目链接：669. 修剪二叉搜索树
🔔 解题思路
解法一：递归
利用BST树的性质，要明确当下节点可能 不再[low, high]区间内，但是其左子树或者右子树是存在这样的节点的；
自底而上不断改变树的结构，剔除不再[low,high]的节点，有：
- 当前节点val < low ，那么它的右子树一定是在[low， high]区间内；
- 相同的，val >high, 那么它的左子树一定在[low， high]区间内
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) return nullptr;
// 自底向上改变
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
if (root->val > high) return root->left;
else if (root->val < low) return root->right;
else return root;
}
};
解法二：迭代
看代码注释即可，思考应该返回什么？怎么修剪左右子树？
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
// 找到第一个符合[low, high] 的节点（当返回值）；
while (root && (root->val < low || root->val > high)) {
if (root->val < low) root = root->right; // 当前值 < low
else root = root->left; // 当前值 > low
}
// 修剪左子树
TreeNode* cur =root;
while (cur != nullptr) {
while (cur->left && cur->left->val < low) { //找到符合[low, high]的节点 接入left
cur->left = cur->left->right;
}
cur = cur->left;
}
// 修剪右子树
cur = root;
while (cur != nullptr) {
while (cur->right && cur->right->val > high) { //找到符合[low, high]的节点 接入right
cur->right = cur->right->left;
}
cur = cur->right;
}
return root;
}
};
💥 复杂度分析
- 时间复杂度：O(n);
- 空间复杂度：O(1);
Original: https://www.cnblogs.com/D-booker/p/16365889.html
Author: D-booker
Title: 19. 二叉搜索树的插入删除修剪
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/713327/
转载文章受原作者版权保护。转载请注明原作者出处！