LeetCode 450 删除二叉搜索树中的节点

发布于:2021-09-16 23:20:53

分析
二叉搜索树的递归框架如下:

TreeNode* BST(TreeNode* root, int target){
if(root != nullptr) return root;
if(root -> val == target){
//找到目标,该做什么
}else if(root -> val < target){
root -> right = BST(root -> right, target);
}else{
root -> left = BST(root -> left, target);
}
return root;
}

作为删除操作,找到的情况可以分为3种情况:
1)A恰好是末端节点,两个子节点都是空的,那么这时候把它删除即可,返回null。
2)A只有一个非空子节点,那么它要让这个孩子接替自己的位置
3)A有两个子节点,A必须找到A.val的前驱后后继代替它,并递归的删除它的代替结点。
需要注意的是,通过这道题目要牢记二叉搜索树的递归框架


代码

class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(nullptr == root) return root;

if(root -> val == key){
找到了,怎么操作
if(root -> left == nullptr) return root -> right;
if(root -> right == nullptr) return root -> left;

TreeNode* minNode = getMin(root -> right);
root -> val = minNode -> val;
root -> right = deleteNode(root -> right, minNode -> val);
}else if(root -> val < key){
//去找右子树
root -> right = deleteNode(root ->right, key);
}else{
//去找左子树
root -> left = deleteNode(root ->left, key);
}
return root;
}

TreeNode* getMin(TreeNode* root){
//返回以root为根节点的二叉搜索树中最小的结点
while(root -> left != nullptr) root = root -> left;
return root;
}
};

相关推荐

最新更新

猜你喜欢