插入二叉搜索树

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

热度指数：677 时间限制：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，点此查看相关信息

算法知识视频讲解

Java

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号

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)

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

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)