首页 > 试题广场 >

插入二叉搜索树

[编程题]插入二叉搜索树
  • 热度指数：677 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一棵二叉搜索树的根节点和一个插入值 val。请你把这个 val 插入二叉搜索树中并保持这棵树依然是二叉搜索树。你可以返回任意一个合法结果。

例如：输入二叉树，插入一个 4 ，可能的结果有，等等，返回任意一个即可。

数据范围：二叉搜索树节点数满足 ，二叉搜索树上节点值满足
示例1

输入

{2,1,3},4

输出

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

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

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
找工作的基米花头像 找工作的基米花 
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)
Java
17c89头像 17c89 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

/**
 * NC372 插入二叉搜索树
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 树的问题 -> 终究是要转化为树的遍历问题(前序 中序 后序 层序)
     * 
     * @param root TreeNode类 
     * @param val int整型 
     * @return TreeNode类
     */
    public TreeNode insertToBST (TreeNode root, int val) {
        preOrder(root, val);

        return root;
    }

    /**
     * 前序遍历
     * @param root
     * @param val
     */
    private void preOrder(TreeNode root, int val){
        if(root == null){
            return;
        }

        int num = root.val;
        
        if(val < num){
            if(root.left == null){
                root.left = new TreeNode(val);
            }else{
                preOrder(root.left, val);
            }
        }else{
            if(root.right == null){
                root.right = new TreeNode(val);
            }else{
                preOrder(root.right, val);
            }
        }
    }
}

发表于 2025-01-24 13:21:44 回复(0)
Java
牛客499848474号头像 牛客499848474号 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param val int整型
     * @return TreeNode类
     */
    public TreeNode insertToBST (TreeNode root, int val) {
        // write code here
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode cur = root;
        while (cur.val != val) {
            if (val < cur.val) {
                if (cur.left == null) {
                    cur.left = new TreeNode(val);
                }
                cur = cur.left;
            } else {
                if (cur.right == null) {
                    cur.right = new TreeNode(val);
                }
                cur = cur.right;
            }
        }
        return root;
    }
}

发表于 2025-01-15 11:16:42 回复(0)
Rust
老刘001头像 老刘001 
/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution{

}

type T = Option<Box<TreeNode>>;
use std::cmp::Ordering::{Less, Equal, Greater};

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param root TreeNode类 
        * @param val int整型 
        * @return TreeNode类
    */
    pub fn insertToBST(&self, mut root: T, val: i32) -> T {
        // write code here
        if root.is_none() {
            Some(Box::new(TreeNode::new(val)))
        } else {
            Self::insert(&mut root, val);
            root
        }
    }
    fn insert(mut node: &mut T, val: i32){
        loop {
            match val.cmp(&node.as_ref().unwrap().val) {
                Less => {
                    if node.as_mut().unwrap().left.is_none() {
                        node.as_mut().unwrap().left = Some(Box::new(TreeNode::new(val)));
                        break;
                    } else {
                        node = &mut node.as_mut().unwrap().left;
                    }
                },
                Greater => {
                    if node.as_mut().unwrap().right.is_none() {
                        node.as_mut().unwrap().right = Some(Box::new(TreeNode::new(val)));
                        break;
                    } else {
                        node = &mut node.as_mut().unwrap().right;
                    }
                },
                Equal => {
                    todo!();
                },
            };
        };
    }
}

发表于 2023-07-27 00:00:58 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
//import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param val int整型 
 * @return TreeNode类
*/
func insertToBST( root *TreeNode ,  val int ) *TreeNode {
    if root==nil{
        return &TreeNode{Val:val}
    }else if root.Val>val{
        root.Left=insertToBST(root.Left,val)
        return root
    }else{
        root.Right=insertToBST(root.Right,val)
        return root
    }
}

发表于 2023-03-15 17:28:55 回复(0)
Python2
菜鸡升职记头像 菜鸡升职记 
# -*- coding: utf-8 -*-


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class BT:
    def __init__(self):
        self.root = None

    def levelOrderToBT(self, nums):
        n = len(nums)

        if n > 0:
            self.root = TreeNode(nums[0])
            queue, idx = [self.root], 1

            while queue and idx < n:
                node = queue.pop(0)
                node.left = TreeNode(nums[idx]) \
                    if nums[idx] != None else None
                if node.left:
                    queue.append(node.left)
                node.right = TreeNode(nums[idx + 1]) \
                    if idx + 1 < n and nums[idx + 1] != None else None
                if node.right:
                    queue.append(node.right)
                idx += 2

        return self.root

    @staticmethod
    def levelOrder(root):
        if not root:
            return []

        res, queue = [], [root]
        while queue:
            node = queue.pop(0)
            if node:
                res.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append(None)

        while res and res[-1] == None:
            res.pop()

        return res


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @param val int整型
# @return TreeNode类
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/4900db9ddfbd43a7a9841c6a408bacf2?tpId=196&tqId=40503&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        搜索二叉树的插入，使用双指针parent、cur分别指向待插入位置的父节点和待插入位置，从根节点开始遍历二叉树，寻找插入位置
    复杂度：
        时间复杂度：O(logN)
        空间复杂度：O(1)
    """

    def insertToBST(self, root, val):
        # write code here
        if not root:
            return TreeNode(val)
        parent, cur = None, root
        while cur:
            if cur.val == val:
                return root
            elif cur.val < val:  # 插入右子树
                parent, cur = cur, cur.right
            else:  # 插入左子树
                parent, cur = cur, cur.left
        if parent.val > val:
            parent.left = TreeNode(val)
        elif parent.val < val:
            parent.right = TreeNode(val)
        return root


if __name__ == "__main__":
    sol = Solution()

    nums, val = [2, 1, 3], 4

    bt = BT()
    bt1 = bt.levelOrderToBT(nums)
    print BT.levelOrder(bt1)

    res = sol.insertToBST(bt1, val)
    print BT.levelOrder(res)

发表于 2022-06-27 11:11:03 回复(0)
Java
唐喻铭头像 唐喻铭 
import java.util.*;

public class Solution {
    public TreeNode insertToBST (TreeNode root, int val) {
        if(root == null) 
            return null;
        TreeNode cur = root;//用于遍历
        TreeNode p = cur;//用于记录cur的位置
        while(cur != null) {
            if(cur.val > val) {
                p = cur;
                cur = cur.left;//放左边
            }else {
                p = cur;
                cur = cur.right;//放右边
            }
        }
        TreeNode node = new TreeNode(val);
        if(p.val > val) {
            p.left = node;
        }else {
            p.right = node;
        }
        return root;
    }
}


发表于 2022-05-23 20:45:03 回复(0)
Java
Isolated_Island头像 Isolated_Island 
import java.util.*;

public class Solution {
    public TreeNode insertToBST (TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode head = root;
        while (true) {
            if (root.val < val) {
                if (root.right == null) {
                    root.right = new TreeNode(val);
                    break;
                }
                root = root.right;
            } else if (root.val > val) {
                if (root.left == null) {
                    root.left = new TreeNode(val);
                    break;
                }
                root = root.left;
            } else {
                break;
            }
        }
        return head;
    }
}

发表于 2022-05-17 17:33:50 回复(0)
提交观点

问题信息

二分 树
难度：
8条回答 4342浏览

热门推荐

通过挑战的用户

查看代码

相关试题

插入二叉搜索树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号