首页 > 试题广场 >

插入二叉搜索树

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

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

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

输入

{2,1,3},4

输出

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

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
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)
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)

问题信息

难度:
2条回答 1933浏览

热门推荐

通过挑战的用户

查看代码