C++ 解法, 执行用时: 38ms, 内存消耗: 12620KB, 提交时间: 2022-06-15
static const auto io_sync_off = []() {
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
return nullptr;
}
();
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root)
return root;
if (root->val == key) {
if (!root->left && !root->right) {
delete root;
return NULL;
} else if (!root->left) {
TreeNode* node = root->right;
delete root;
return node;
} else if (!root->right) {
TreeNode* node = root->left;
delete root;
return node;
} else {
TreeNode* cur = root->right;
while (cur->left)
cur = cur->left;
cur->left = root->left;
TreeNode* temp = root;
root = root->right;
delete temp;
return root;
}
}
if (root->val > key)
root->left = deleteNode(root->left, key);
if (root->val < key)
root->right = deleteNode(root->right, key);
return root;
}
};
C++ 解法, 执行用时: 38ms, 内存消耗: 12632KB, 提交时间: 2022-05-29
static const auto io_sync_off = [](){
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root)
return root;
if(root->val==key)
{
if(!root->left&&!root->right)
{
delete root;
return NULL;
}
else if(!root->left)
{
TreeNode* node=root->right;
delete root;
return node;
}
else if(!root->right)
{
TreeNode* node=root->left;
delete root;
return node;
}
else
{
TreeNode* cur=root->right;
while(cur->left)
cur=cur->left;
cur->left=root->left;
TreeNode* temp=root;
root=root->right;
delete temp;
return root;
}
}
if(root->val>key)
root->left=deleteNode(root->left,key);
if(root->val<key)
root->right=deleteNode(root->right,key);
return root;
}
};
C++ 解法, 执行用时: 43ms, 内存消耗: 9484KB, 提交时间: 2022-07-13
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param key int整型
* @return TreeNode类
*/
TreeNode* parent = NULL;
TreeNode* left = NULL;
TreeNode* right = NULL;
TreeNode* target = NULL;
TreeNode* deleteNode(TreeNode* root, int key) {
// write code here
findTargetNode(root, NULL, key);
if(!target) return root;
if(right){
if(left){
TreeNode* rl = right->left;
TreeNode* rpre = right;
while(rl){
rpre = rl;
rl = rl->left;
// rpre = rl;
}
rpre->left = left;
}
if(parent){
if(target->val <= parent->val ) parent->left = right;
else parent->right = right;
delete target;
return root;
}
else return right;
}
if(left){
if(parent){
if(target->val <= parent->val ) parent->left = left;
else parent->right = left;
delete target;
return root;
}
else return left;
}else{
if(root == target) return NULL;
else {
if(target->val <= parent->val ) parent->left = NULL;
else parent->right = NULL;
delete target;
return root;
}
}
}
void findTargetNode(TreeNode* root, TreeNode* from, int key){
if(!root) return;
if(root->val == key){
target = root;
parent = from;
left = root->left;
right = root->right;
}
if(key <= root->val) findTargetNode(root->left, root, key);
else findTargetNode(root->right, root, key);
}
};
C++ 解法, 执行用时: 43ms, 内存消耗: 9520KB, 提交时间: 2022-04-30
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution
{
public:
int lr;
vector<TreeNode *> findNode(TreeNode *root, int key, TreeNode *father)
{
if (root == nullptr)
return {nullptr, nullptr};
// cout << root->val << endl;
if (root->val == key)
return {root, father};
if (key < root->val && root->left != nullptr)
{
lr = 0;
return findNode(root->left, key, root);
}
if (key > root->val && root->right != nullptr)
{
lr = 1;
return findNode(root->right, key, root);
}
return {nullptr, nullptr};
}
TreeNode *deleteNode(TreeNode *root, int key)
{
lr = -1;
vector<TreeNode *> node = findNode(root, key, nullptr);
if (node[0] != nullptr)
{
// cout << "val:" << (node[0]->val) << " " << (node[1]->val) << endl;
if (node[0]->left == nullptr)
node[0] = node[0]->right;
else if (node[0]->right == nullptr)
node[0] = node[0]->left;
else
{
TreeNode *right_leftTree = node[0]->right;
while (right_leftTree->left != nullptr)
{
right_leftTree = right_leftTree->left;
}
right_leftTree->left = node[0]->left;
node[0] = node[0]->right;
}
if (node[1] != nullptr)
{
if (lr == 0)
{
node[1]->left = node[0];
}
else
{
node[1]->right = node[0];
}
}
else
{
if (root != nullptr)
root = node[0];
}
}
return root;
}
};
C++ 解法, 执行用时: 43ms, 内存消耗: 11008KB, 提交时间: 2022-02-22
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param key int整型
* @return TreeNode类
*/
TreeNode* deleteNode(TreeNode* root, int key) {
// write code here
if(!root) return nullptr;
if(root -> val > key) root -> left = deleteNode(root -> left, key);
else if(root -> val < key) root -> right = deleteNode(root -> right, key);
else{
if(!root -> left || !root -> right) return root -> left ? root -> left : root -> right;
TreeNode* tmp = root -> left;
while(tmp -> right){
tmp = tmp -> right;
}
tmp -> right = root -> right;
return root -> left;
}
return root;
}
};
