LeetCode 450 [Delete Node in a BST]

题目链接

题目描述

  • 给定一颗二叉排序树的根结点以及一个值,要求删除二叉排序树中包含该值的结点,同时返回该树的最新的根结点。一般来说,删除可以通过两个步骤来完成,一是查找该结点,二是删除该结点(如果存在的话)。时间复杂度必须是O(h),h表示树的高度。

解题思路

  • 题目默认条件

    • 若非特殊说明,二叉排序树不存在两个或多个结点包含同个值的情况。
  • 查找“待删除结点”的步骤

    1. 从根结点开始查找,将当前结点的值与给定的值进行比较。
    2. 如果当前结点的值比较大,则将当前结点的左结点设置为新的当前结点;如果当前结点的值比较小,则将当前结点的右结点设置为新的当前结点;如果值相等,则说明当前结点即为目标,结束查找过程。
    3. 若当前结点为NULL,也结束查找过程。
    4. 查找过程需要记录“待删除结点”的父结点,同时还要记录它是父结点的左孩子还是右孩子(下文使用“方向”来表示这个信息)。
  • 删除“待删除结点”的步骤

    1. 若第一步查找不到“待删除结点”,则不需要执行删除操作,返回当前的根结点即可。
    2. 若找到了要“待删除结点”,则需要分以下几种情况考虑
      • 情况1:“待删除结点”没有任何子结点
        • 如果“待删除结点”是根结点(即它的父结点为NULL),那么释放该结点,返回NULL,结束删除过程
        • 如果“待删除结点”不是根结点,那么释放该结点,同时将它的父结点的对应方向的子结点置为NULL,结束删除过程
      • 情况2:“待删除结点”只有左子结点
        • 如果“待删除结点”是根结点(即它的父结点为NULL),那么释放该结点,返回它的左子结点,结束删除过程
        • 如果“待删除结点”不是根结点,那么释放该结点,同时将它的父结点的对应方向的子结点置为它的左结点,结束删除过程
      • 情况3:待删除的结点只有右子结点(与情况2非常类似)
        • 如果“待删除结点”是根结点(即它的父结点为NULL),那么释放该结点,返回它的右子结点,结束删除过程
        • 如果“待删除结点”不是根结点,那么释放该结点,同时将它的父结点的对应方向的子结点置为它的右结点,结束删除过程
      • 情况4:“待删除结点”同时包含左右子结点
        • 这种情况下,我们的目标是找一个最合适的结点(下文使用“待交换结点”来表示它)来取代“待删除结点”的位置。二叉排序树的特性就是每一个结点都比它左子树的所有结点大,同时比它右子树的所有结点小。因此“待交换结点”要么是左子树中值最大的结点,要么是右子树中值最小的结点。后续描述使用右子树中值最小的结点作为“待交换结点”,左子树中值最大的结点理论上满足题目要求,但我未实际测试。
        • 查找“待交换结点”的步骤
          1. 从“待删除结点”的右子结点开始,查找以它为根的子树中值最小的结点,查找过程同样需要记录当前结点的父结点及方向
          2. 二叉排序树中值最小的结点必定位于最左侧,因此只要当前结点存在左子结点,则持续将左子结点置为新的当前结点即可
          3. 最后一个不包含左子结点的当前结点,就是“待交换结点”
        • “待交换结点”是必定存在的,既然找到了,就可以开始删除步骤了。题目并未要求实际删除该结点,因此通过变更该结点的值也可以实现类似功能。这里要做的,只是简单地把“待交换结点”的值赋给“待删除结点”。
        • 最后要处理“待交换结点”,上文只说了它不包含左子结点,因此要考虑它是否存在右结点。如果它存在右结点,那么它的父结点的对应方向的子结点就是它的右结点,否则它的父结点的对应方向的子结点就是NULL。最后把“待交换结点”释放了即可。

C++代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode* node2Del = root;
TreeNode* parentOfNode2Del = NULL;
int direction = 0;
// find the node 2 delete and its parent
while (node2Del) {
if (node2Del->val == key) {
break;
} else if (node2Del->val > key) {
parentOfNode2Del = node2Del;
node2Del = node2Del->left;
direction = -1;
} else {
parentOfNode2Del = node2Del;
node2Del = node2Del->right;
direction = 1;
}
}
// node to delete not found, do nothng and return root
if (!node2Del) {
return root;
}
if (!node2Del->left && !node2Del->right) { // node to delete has no child
// node to delete is root
if (!parentOfNode2Del) {
delete root;
return NULL;
}
// node to delete is not root
delete node2Del;
if (direction < 0) {
parentOfNode2Del->left = NULL;
} else {
parentOfNode2Del->right = NULL;
}
} else if (node2Del->left && !node2Del->right) { // node to delete has only left child
// node to delete is root
if (!parentOfNode2Del) {
delete root;
return root->left;
}
// node to delete is not root
if (direction < 0) {
parentOfNode2Del->left = node2Del->left;
} else {
parentOfNode2Del->right = node2Del->left;
}
delete node2Del;
} else if (node2Del->right && !node2Del->left) { // node to delete has only right child
// node to delete is root
if (!parentOfNode2Del) {
delete root;
return root->right;
}
// node to delete is not root
if (direction < 0) {
parentOfNode2Del->left = node2Del->right;
} else {
parentOfNode2Del->right = node2Del->right;
}
delete node2Del;
} else { // node to delete has both left and right child
// find the least value of right sub tree
TreeNode* node2Switch = node2Del->right;
TreeNode* parentOfNode2Switch = node2Del;
int directionSwitch = 1;
while (node2Switch->left) {
parentOfNode2Switch = node2Switch;
node2Switch = node2Switch->left;
directionSwitch = -1;
}
// switch value
node2Del->val = node2Switch->val;
if (directionSwitch < 0) {
parentOfNode2Switch->left = node2Switch->right;
} else {
parentOfNode2Switch->right = node2Switch->right;
}
delete node2Switch;
}
return root;
}
};