701.二叉搜索树中的插入操作 (Medium)*

题目描述*

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

代码*

递归或迭代。

递归迭代

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr) {
            return new TreeNode(val);
        }
        if(root->val > 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) {
        TreeNode *cur = root;
        while(cur != nullptr) {
            if(cur->val > val) {
                if(cur->left == nullptr) {
                    cur->left = new TreeNode(val);
                    return root;
                }else {
                    cur = cur->left;
                }
            }else {
                if(cur->right == nullptr) {
                    cur->right = new TreeNode(val);
                    return root;
                }else {
                    cur = cur->right;
                }
            }
        }
        return new TreeNode(val);
    }
};

最后更新: July 23, 2022