二叉排序树的删除根节点

二叉排序树是一种特殊的二叉树，它的左子树上的所有节点的值都小于根节点的值，右子树上的所有节点的值都大于根节点的值。因此，删除根节点时需要特别处理，本文将从多个角度分析如何删除二叉排序树的根节点。

1. 删除根节点的情况

删除根节点时，需要考虑以下几种情况：

1.1 没有右子树

如果没有右子树，直接将根节点的左子树成为树的新根。

1.2 没有左子树

如果没有左子树，直接将根节点的右子树成为树的新根。

1.3 左右子树都存在

如果左右子树都存在，有两种处理方法：

（1）直接将根节点的左子树的最右下节点的右子树指向根节点的右子树，将根节点的左子树成为树的新根。

（2）将根节点的右子树的最左下节点的左子树指向根节点的左子树，将根节点的右子树成为树的新根。

2. 代码实现

对于第一种情况，代码如下：

```

TreeNode* deleteNode(TreeNode* root) {

if (!root) return NULL;

if (!root->right) return root->left;

TreeNode* cur = root->right;

while (cur->left) cur = cur->left;

cur->left = root->left;

return root->right;

}

```

对于第二种情况，代码如下：

```

TreeNode* deleteNode(TreeNode* root) {

if (!root) return NULL;

if (!root->left) return root->right;

TreeNode* cur = root->left;

while (cur->right) cur = cur->right;

cur->right = root->right;

return root->left;

}

```

对于第三种情况，代码如下：

```

TreeNode* deleteNode(TreeNode* root) {

if (!root) return NULL;

if (!root->left) return root->right;

if (!root->right) return root->left;

TreeNode* cur = root->left;

while (cur->right) cur = cur->right;

cur->right = root->right;

return root->left;

}

```

3. 时间复杂度分析

以上三种情况的时间复杂度均为O(h)，其中h为树的高度。如果树已经是平衡的，时间复杂度为O(logn)，其中n为节点数。但是如果树是单边增长的，时间复杂度将退化为O(n)，其中n为节点数。

4. 空间复杂度分析

以上三种情况的空间复杂度均为O(1)，不需要额外的空间来存储节点。