删除二叉排序树的代码
二叉排序树是一种特殊的二叉树，它保证了左子树的所有节点值均小于根节点，右子树的所有节点值均大于根节点。在进行删除操作时，需要注意叶子节点和只有一个孩子的节点的情况。本文将从多个角度分析删除二叉排序树的代码，并给出全文摘要和3个关键词。
1. 递归删除
递归删除是一种常见的删除二叉排序树节点的方法。其主要思想是从根节点开始比较，找到要删除的节点后，分三种情况讨论：
（1）要删除的节点为叶子节点：直接删除该节点即可；
（2）要删除的节点只有一个孩子：将该节点的父节点指向该节点的孩子节点即可；
（3）要删除的节点有两个孩子：找到该节点的右子树中最小的节点（即比要删除的节点大的最小值），用该节点替换要删除的节点，在删除该最小节点时则回到（1）或（2）的情况。
递归删除的代码实现如下：
```c++
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (key < root->val) root->left = deleteNode(root->left, key);
else if (key > root->val) root->right = deleteNode(root->right, key);
else {
if (!root->left) return root->right;
else if (!root->right) return root->left;
TreeNode* minNode = findMin(root->right);
root->val = minNode->val;
root->right = deleteNode(root->right, root->val);
}
return root;
}
TreeNode* findMin(TreeNode* node) {
while (node->left) node = node->left;
return node;
}
```
2. 非递归删除
非递归删除是另一种实现删除二叉排序树节点的方法。其主要思想是使用一个指针p指向要删除的节点，并记录该节点的父节点parent。分三种情况讨论：
（1）要删除的节点为叶子节点：直接删除该节点即可；
（2）要删除的节点只有一个孩子：将该节点的父节点指向该节点的孩子节点即可；
（3）要删除的节点有两个孩子：找到该节点的右子树中最小的节点（即比要删除的节点大的最小值），用该节点替换要删除的节点，在删除该最小节点时则回到（1）或（2）的情况。
非递归删除的代码实现如下：
```c++
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
TreeNode *p = root, *parent = nullptr;
while (p && p->val != key) {
parent = p;
if (key < p->val) p = p->left;
else p = p->right;
}
if (!p) return root;
if (p->left && p->right) {
TreeNode* minNode = p->right;
while (minNode->left) {
parent = minNode;
minNode = minNode->left;
}
p->val = minNode->val;
p = minNode;
}
TreeNode* child = nullptr;
if (p->left) child = p->left;
else if (p->right) child = p->right;
if (!parent) root = child;
else if (parent->left == p) parent->left = child;
else parent->right = child;
return root;
}
```
3. 删除的复杂度分析
删除二叉排序树节点的操作最坏情况下需要遍历整棵树，时间复杂度为O(n)，其中n为二叉树的节点数。平均情况下，二叉排序树高度为O(logn)，因此删除节点的操作平均时间复杂度为O(logn)。
4.
