插入二叉搜索树

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

热度指数：535 时间限制：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}

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

算法知识视频讲解

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)