450. 删除二叉搜索树中的节点
2019-11-10 本文已影响0人
一川烟草_满城风絮_梅子黄时雨
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr)
return root;
if (root-> val == key)
{
if (root -> left == NULL) // 如果左子树为空,那么直接返回右子树
{
return root -> right;
}
auto cur = root -> left;
auto pre = root;
while(cur -> right)
{
pre = cur;
cur = cur -> right;
}
// cur为等待删除节点,pre为cur的父节点
if (pre == root) // 如果pre为root节点,那么直接把root的右子树挂到cur的右子树
{
cur -> right = root -> right;
return cur;
}
else
{
pre -> right = cur -> left;
cur -> left = root -> left;
cur -> right = root -> right;
return cur;
}
}
else
{
root -> left = deleteNode(root -> left, key);
root -> right = deleteNode(root -> right, key);
return root;
}
}
};