点击：题目链接：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
思路
搜索二叉树的原理：左子树的值永远小于根节点，右子树的值永远大于根节点。
- 无右子树，遍历左子数中最大的右节点
- 无左子树，遍历右子树，遵循1
- 有左子树和右子树，遍历右子树，遵循1
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
else if (key > root->val) root->right = deleteNode(root->right, key);
else if (key < root->val) root->left = deleteNode(root->left, key);
else {
if (root->right == nullptr) return root->left;
else if (root->left == nullptr) return root->right;
else {
TreeNode* temp = root->right;
while(temp->left)
temp = temp->left;
temp->left = root->left;
root = root->right;
}
}
return root;
}
};
|
复杂度：
时间：O（log（n）） 空间：O（log(n)）