1. question: 二叉搜索树中的插入操作(中等)
给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/insert-into-a-binary-search-tree
示例 1:
1 2 3
| 输入:root = [4,2,7,1,3], val = 5 输出:[4,2,7,1,3,5] 解释:另一个满足题目要求可以通过的树是:
|
示例 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
这道题,怎么说呢?有两种方法来做:
- 一种是简单的,即将新插入的值作为一个子节点,此时只需要找到其父节点即可。因为二叉搜索树的节点值是有顺序的,只需要类似二分查找,遍历到null即可。
- 另一种比较复杂,即将新插入的值作为某棵子树的根节点,这就需要重构二叉搜索树。暂时不这样做了,感觉没有意义。
第一种简单方法如下所示:
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; }
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)。