/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* traversal(TreeNode* cur , int key)
    {
      //当为空节点的时候直接返回
        if(cur==nullptr) return cur;
    //当前值为目标值时
        if(cur->val == key)
        {
          //当前点的左右子树都是空，删除节点返回
            if(cur->left == nullptr && cur->right == nullptr) 
            {
                delete cur;
                return nullptr;
            }
            //左子树存在，右子树空，左孩子作为新的根节点返回
            else if(cur->left != nullptr && cur->right == nullptr)
            {
                auto tmp = cur->left;
                delete cur;
                return tmp;
            }
            //左子树为空，右子树存在，右子树作为新的根节点返回
            else if(cur->left == nullptr && cur->right != nullptr)
            {
                auto tmp = cur->right;
                delete cur;
                return tmp;
            }
            //左右子树都存在，令右孩子为新的根节点，左子树放到右子树的最左边。
            else
            {
                TreeNode* tmp = cur->right;
                while(tmp->left !=nullptr)
                {
                    tmp = tmp->left;
                }
                tmp->left = cur->left;
                TreeNode* result = cur->right;
                delete cur;
                return result;
            }
        }
        //当前值不是目标值，按照二叉搜索树单边遍历
        if(cur->val > key) cur->left = traversal(cur->left , key);
        if(cur->val < key) cur->right = traversal(cur->right , key);
        return cur;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr) return nullptr;
        return traversal(root,key);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* track_back(TreeNode* cur , int key)
    {
        if(cur == nullptr) return nullptr;
        else if(cur->left == nullptr && cur->right == nullptr && cur->val == key) return nullptr;
        else if(cur->left == nullptr && cur->right != nullptr && cur->val == key) return cur->right;
        else if(cur->left != nullptr && cur->right == nullptr && cur->val == key) return cur->left;
        if(cur->val == key)
        {
            TreeNode* tmp = cur->right;
            while(tmp->left != nullptr)
                tmp = tmp->left;
            tmp->left = cur->left;
            return  cur->right;
        }
        if(cur->val > key) cur->left = track_back(cur->left , key);
        if(cur->val < key) cur->right = track_back(cur->right , key);
        return cur;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        return track_back(root,key);
    }
};