- 如果在根节点，怎么操作？
迭代需要处理根节点的特殊情况，而递归不需要特殊处理。
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
int compar(int a, int b) {
if(a > b) return 1;
else if(b > a) return -1;
return 0;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root)
return nullptr;
int cmp = compar(root->val, key);
if(cmp < 0) {
root->right = deleteNode(root->right, key);
} else if(cmp > 0) {
root->left = deleteNode(root->left, key);
} else {
if(!root->left) return root->right;
if(!root->right) return root->left;
auto rm = min(root->right);
root->right = deleteMin(root->right);
rm->left = root->left;
rm->right = root->right;
root = rm;
}
return root;
}
TreeNode* min(TreeNode* root) {
if(!root->left)
return root;
return min(root->left);
}
TreeNode* deleteMin(TreeNode* root) {
if(!root->left)
return root->right;
root->left = deleteMin(root->left);
return root;
}
};
|
迭代实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| class Solution {
public:
int compar(int a, int b) {
if(a > b) return 1;
else if(b > a) return -1;
return 0;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root)
return nullptr;
TreeNode* node = root, *prev_node = nullptr;
bool is_left =false;
while(node) {
int cmp = compar(node->val, key);
if(cmp > 0) {
prev_node = node;
node = node->left;
is_left = true;
}
else if(cmp < 0) {
prev_node = node;
node = node->right;
is_left = false;
} else
break;
}
if(!node && prev_node)
return root;
if(!node->left && !node->right) {
if(!prev_node) return nullptr;
if(is_left) prev_node->left = nullptr;
else prev_node->right = nullptr;
}
else if (node->left && !node->right) {
if(!prev_node) return node->left;
if(is_left) prev_node->left = node->left;
else prev_node->right = node->left;
}
else if (node->right && !node->left) {
if(!prev_node) return node->right;
if(is_left) prev_node->left = node->right;
else prev_node->right = node->right;
} else {
int min_val = min(node->right);
node->val = min_val;
node->right = deleteMin(node->right);
}
return root;
}
int min(TreeNode* node) {
while(node->left)
node = node->left;
return node->val;
}
TreeNode* deleteMin(TreeNode* node) {
if(!node->left)
return node->right;
node->left = deleteMin(node->left);
return node;
}
};
|
Accepted
85/85 cases passed (24 ms)
Your runtime beats 90.96 % of cpp submissions
Your memory usage beats 5.26 % of cpp submissions (17.6 MB)
