leetcode-删除二叉搜索树中的节点

点击:题目链接:给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
说明: 要求算法时间复杂度为 O(h),h 为树的高度。

思路

搜索二叉树的原理:左子树的值永远小于根节点,右子树的值永远大于根节点。

  1. 无右子树,遍历左子数中最大的右节点
  2. 无左子树,遍历右子树,遵循1
  3. 有左子树和右子树,遍历右子树,遵循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))

作者

Dylan Zhu

发布于

2021-04-17

更新于

2021-04-17

许可协议

评论

:D 一言句子获取中...