LeetCode_74_InsertIntoABinarySearchTree


1. question: 二叉搜索树中的插入操作(中等)

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/insert-into-a-binary-search-tree

示例 1:

示例1

1
2
3
输入:root = [4,2,7,1,3], val = 5
输出:[4,2,7,1,3,5]
解释:另一个满足题目要求可以通过的树是:

示例1s

示例 2:

1
2
输入:root = [40,20,60,10,30,50,70], val = 25
输出:[40,20,60,10,30,50,70,null,null,25]

示例 3:

1
2
输入:root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出:[4,2,7,1,3,5]

提示:

1
2
3
4
5
树中的节点数将在 [0, 104]的范围内。
-108 <= Node.val <= 108
所有值 Node.val 是 独一无二 的。
-108 <= val <= 108
保证 val 在原始BST中不存在。

2. answers

这道题,怎么说呢?有两种方法来做:

  1. 一种是简单的,即将新插入的值作为一个子节点,此时只需要找到其父节点即可。因为二叉搜索树的节点值是有顺序的,只需要类似二分查找,遍历到null即可。
  2. 另一种比较复杂,即将新插入的值作为某棵子树的根节点,这就需要重构二叉搜索树。暂时不这样做了,感觉没有意义。

第一种简单方法如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class Solution_0073 {

public TreeNode insertIntoBST(TreeNode root, int val) {

if(root == null) return new TreeNode(val);

// 保留结果
TreeNode result = root;

// 保存要插入位置的父节点
TreeNode pre = root;

// 找到要插入位置的父节点
while(root != null) {

pre = root;

if(root.val > val) root = root.left;
else root = root.right;
}

// 此时,pre保存的就是要插入位置的父节点
if(pre.val > val) pre.left = new TreeNode(val);
else pre.right = new TreeNode(val);

return result;
}

public static void main(String[] args) {
System.out.println();

TreeNode tn5 = new TreeNode(3);
TreeNode tn4 = new TreeNode(1);
TreeNode tn3 = new TreeNode(2, tn4, tn5);
TreeNode tn2 = new TreeNode(7);
TreeNode tn1 = new TreeNode(4, tn3, tn2);

Solution_0073 s = new Solution_0073();

TreeNode result = s.insertIntoBST(tn1, 5);

// 层序遍历
Queue<TreeNode> queue = new LinkedList<>();

queue.offer(result);

while(queue.size() > 0 ) {

int length = queue.size();

while(length-- > 0) {

result = queue.poll();

System.out.print(result.val + "\t");

if(result.left != null) queue.offer(result.left);
if(result.right != null) queue.offer(result.right);

}

System.out.println();
}
}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录