插入二叉搜索树

[编程题]插入二叉搜索树

热度指数：632 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉搜索树的根节点和一个插入值 val。请你把这个 val 插入二叉搜索树中并保持这棵树依然是二叉搜索树。你可以返回任意一个合法结果。

例如：输入二叉树

，插入一个 4 ，可能的结果有

，

等等，返回任意一个即可。

数据范围：二叉搜索树节点数满足 $1 \le n \le 10^5 \$ ，二叉搜索树上节点值满足 $1 \le val \le 10^9 \$

示例1

输入

{2,1,3},4

输出

{2,1,3,#,#,#,4}

备注:

递归到相应的位置，插入 val。
如果当前节点为空，插入。
如果当前节点比val大时，递归左儿子。
如果当前节点比val小时，递归右儿子。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

fatzard

void insert(struct TreeNode* root,int val)
{
    if(root)
    {
        if(root->val>val)
        {
            if(root->left)insert(root->left,val);
            else{
                struct TreeNode* newnode=(struct TreeNode*)malloc(sizeof(struct TreeNode));
                newnode->val=val;
                root->left=newnode;
            }
        }else{
            if(root->right)insert(root->right,val);
            else{
                struct TreeNode* newnode=(struct TreeNode*)malloc(sizeof(struct TreeNode));
                newnode->val=val;
                root->right=newnode;
            }
        }
    }
}
struct TreeNode* insertToBST(struct TreeNode* root, int val ) {
    if(root==NULL){
        struct TreeNode* newnode=(struct TreeNode*)malloc(sizeof(struct TreeNode));
        newnode->val=val;
        root=newnode;
    }
    insert(root, val);
    return root;
}

发表于 2023-10-12 14:47:18 回复(0)