给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
说明: 要求算法时间复杂度为 O(h),h 为树的高度。
来源:力扣(LeetCode)
题目分析
①.二叉搜索树的性质:左子树的节点值都小于根节点值;右子树的节点值都大于根节点值
②.若为叶子节点,则直接删除即可,不影响二叉搜索树的性质
③.若只有一个子树,则用子树取代本节点的位置,不影响二叉搜索树的性质
④.把左子树中的最大值的节点移出,并覆盖到当前节点,不影响二叉搜索树的性质
⑤.通过递归返回修改后的子树,用于更新树的连接关系
代码示例
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if( root == nullptr) return root;
else if( key < root->val )//去左子树上删除,返回删除节点后的左子树
{
root->left = deleteNode(root->left,key);//更新连接关系
}
else if ( key > root->val )//去右子树上删除,返回删除节点后的右子树
{
root->right = deleteNode(root->right,key);//更新连接关系
}
else//删除本节点
{
if( root->right == nullptr && root->left == nullptr)//叶子节点,直接删除
{
delete root;//删除节点
root = nullptr;
return root;
}
else if( root->left != nullptr && root->right == nullptr) //只有左子树,用左子树取代本节点
{
TreeNode * left = root->left ;
root->left = nullptr;//断开连接
delete root;//删除节点
root = nullptr;
return left;
}
else if( root->right != nullptr && root->left == nullptr )//只有右子树,用右子树取代本节点
{
TreeNode * right = root->right ;
root->right = nullptr;//断开连接
delete root;//删除节点
root = nullptr;
return right;
}
else//左右子树都存在
{
//找左子树的最大值
TreeNode * pre = root->left;
while( pre->right != nullptr )
{
pre = pre->right;
}
root->val = pre->val;//更新到当前节点
root->left = deleteNode( root->left,root->val);//去左子树删除原先的节点
return root;//返回自身
}
}
return root;
}
};