题解41 | #插入二叉搜索树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param val int整型 
     * @return TreeNode类
     */
    TreeNode* insertToBST(TreeNode* root, int val) {
        // write code here
        //空树我可就直接诶占领了
        if(root == NULL) {
            TreeNode *newcode = new TreeNode(val);
            return newcode;
        }
        //先找位置，now定位，after同步跟上
        TreeNode *now = root;
        TreeNode *after = root;
        while (now) {
            after = now;
            if(val < now->val){
                now = now->left;
            }
            else {
                now = now->right;
            }
        }
        //now已经指向NULL叶子时 after为待插入的树枝节点
        //找到啊后，pre插入
        TreeNode *newcode = new TreeNode(val);
        if(val < after->val){
            after->left = newcode;
        }
        else {
            after->right = newcode;
        }
        return root;
    }
};

算法思想：

1. 如果根节点为空，则直接创建一个新节点，并将其作为根节点返回。

2. 否则，从根节点开始遍历二叉搜索树，找到合适的插入位置。

3. 如果待插入的值小于当前节点的值，则将当前节点的左子树作为新的当前节点，继续遍历。

4. 如果待插入的值大于当前节点的值，则将当前节点的右子树作为新的当前节点，继续遍历。

5. 当遍历到叶子节点时，将新节点插入到当前节点的左子树或右子树中。

时间复杂度：

最坏情况下，需要遍历整个二叉搜索树，时间复杂度为O(n)，其中n为二叉搜索树的节点数。

空间复杂度：

最坏情况下，递归调用栈的深度为二叉搜索树的高度，空间复杂度为O(logn)，其中n为二叉搜索树的节点数。