/**
 * 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:
    void find_node(TreeNode* cur, int val)
    {
        if(cur==nullptr) return ; 
        //当前值大于目标值，插入左子树
        if(cur->val > val ) 
        {
          //找到空点，插入         .
            if(cur->left == nullptr)
            {
                TreeNode* new_node = new TreeNode(val);
                cur->left = new_node;
            }else
            {
                find_node(cur->left , val);
            }
        }
        //当前值小于目标值，插入右子树
        else if(cur->val <val )  
        {
          //找到空点，插入
             if(cur->right == nullptr)
            {
                TreeNode* new_node = new TreeNode(val);
                cur->right = new_node;
            }else
            {
                find_node(cur->right , val);
            }
        }
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
      //如果根节点是空的，设置新点作为根
        if(root==nullptr ) 
        {
             TreeNode* new_node = new TreeNode(val);
             return new_node;
        }
        else//如果根节点是非空，插入
        {
            find_node(root , val);
            return root;
        }
    }
};

/**
 * 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 val)
    {
        if(cur == nullptr)
        {
            TreeNode *node = new TreeNode(val);
            return node;
        }
        if(cur->val > val) cur->left = track_back(cur->left , val);
        if(cur->val < val) cur->right = track_back(cur->right ,val);
        return cur;
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        return track_back(root,val);
    }
};