450. 删除二叉搜索树中的节点
题目描述
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点； 如果找到了，删除它。
解题思路
思路：使用子树代替删除的节点。如果都有的话，随意左还是右。
通用选择右子树，那么子树的子树如何处理？右子树的右子树变成右子树，右子树的左子树变成被删除节点子树上最右侧叶节点的子树。
class Solution {
public:
int k;
TreeNode*f(TreeNode* r) {if(!r)return r;
if(r->val==k) {
if(!r->left&&!r->right)return 0;
if(!r->left)return r->right;
if(!r->right)return r->left;
TreeNode*save=r->right->left;
r->right->left=r->left;
r=r->right;TreeNode*p=r->left;
while(p->right)p=p->right;p->right=save;
return r;
}
if (r->val<k)r->right=f(r->right);else r->left=f(r->left);return r;
}
TreeNode* deleteNode(TreeNode* r, int key) {
k=key;r=f(r);return r;
}
};