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

/**
* 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) {
		//先找到被删掉的节点为node,它的父节点是fa
		TreeNode* node = root, *fa=root;
		while (node != NULL && node->val != key){
			fa = node;
	        node=node->val>key?node->left:node->right;
        }
		if (node == NULL) return root;
        if(node->left==NULL)//左子树为空
        {
            if(node==root) 
                return root->right;
            if(fa->val>key)
                fa->left=node->right;
            else
                fa->right=node->right;
        }
        else//左子树不为空
        {
            TreeNode* fa1=node->left;
            if(fa1->right==NULL)//左子树的右子树为空
            {
                node->val=fa1->val;
                node->left=fa1->left;
            }
            else//左子树的右子树不为空
            {
                while(fa1->right->right)
                    fa1=fa1->right;
                node->val=fa1->right->val;
                fa1->right=fa1->right->left;
                
            }
        }
        return root;
	}
};