/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

/*

算法思想：

    递归的方法，由于二叉搜索树自带二分的性质，那么首先根结点比较，如果大于根结点值的话，说明肯定要插入到右子树中。所以接下来跟7比较，对于递归函数来说，结点7也可以当作是一个新的根结点，那么由于结点7的值大于目标值5，所以要去其左子树，我们发现其左子结点为空，那么我们就可以根据目标值来生成一个新的结点，然后连到结点7的左子树上即可。那么在递归函数中，首先判断当前结点是否为空，为空的话就新建一个结点返回。否则就判断目标值是否小于当前结点值，是的话就对左子结点调用递归函数，并将返回值赋给当前结点的左子结点，否则就对右子结点调用递归函数，并将返回值赋给当前结点的右子结点，最后返回当前结点即可。

*/

//算法实现：

class Solution {

public:

    TreeNode* insertIntoBST(TreeNode* root, int val) {

        if (!root)

            return new TreeNode(val);

        if (val < root->val)    //目标值小于当前结点值，对左子结点调用递归函数

            root->left = insertIntoBST(root->left, val);

        else

            root->right = insertIntoBST(root->right, val);

        return root;

    }

};

/*

算法思想：

    迭代的方法，首先还是判空，若为空，就新建结点返回。然后用一个变量cur来遍历，在while循环中，如果当前值大于目标值，如果其左子结点不存在，那么我们新建结点，并连上其左子结点，并跳出循环；若左子结点存在，则cur指向其左子结点。否则，当前值小于目标值，若其右子结点不存在，新建结点并连上其右子结点，并跳出循环；若右子结点存在，则cur指向其右子结点。最后返回root即可。

*/

//算法实现：

class Solution {

public:

    TreeNode* insertIntoBST(TreeNode* root, int val) {

        if (!root)

            return new TreeNode(val);

        TreeNode *cur = root;

        while (true) {

            if (cur->val > val) {

                if (!cur->left) {

                    cur->left = new TreeNode(val);

                    break;

                }

                cur = cur->left;

            }

            else {

                if (!cur->right) {

                    cur->right = new TreeNode(val);

                    break;

                }

                cur = cur->right;

            }

        }

        return root;

    }

};