题解

递归和迭代两种解法。

递归解法很直接。

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;
    }
};

迭代的解法：

插入的方式有很多种，不妨选择最简单的。就选择在叶子节点，那么用二分法找到插入位置，然后区分左右即可。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);

        TreeNode* node = root;
        TreeNode* prev = root;

        while(node) {
            prev = node;
            if(val > node->val) {
                node = node->right;
            } else {
                node = node->left;
            }
        }

        if(val > prev->val) {
            prev->right = new TreeNode(val);
        } else {
            prev->left = new TreeNode(val);
        }

        return root;       
    }
};