少女祈祷中...

题目

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

示例1

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

示例2

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

二叉搜索树中的插入操作

提示

  • 给定的树上的节点数介于 0 和 10^4 之间
  • 每个节点都有一个唯一整数值,取值范围从 0 到 10^8
  • -10^8 <= val <= 10^8
  • 新值和原始二叉搜索树中的任意节点值都不同

力扣题目链接

《代码随想录》算法公开课


思路

首先添加结点的位置为叶子结点(不考虑替换中间结点再构建树)。
再来考虑截至条件-当遍历到该结点的子节点都为null时即找到了挂载点。
根据搜索二叉树的特点,即当val大于root结点值时,向右树寻找,当val小于root结点的值时,向左树寻找。
又因为该题提供的二叉树为搜索二叉树,当找到挂载点是,只需判断该值是否大于pre(为循环条件中存储的挂载点)。

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);//当roo为空时,用val值构建结点返回作为头结点
TreeNode newRoot = root;//提前存储头结点,作为返回
TreeNode pre = root;//存储用于挂载的结点
while (root != null) {
pre = root;
if (root.val > val) {//向左树寻找
root = root.left;
} else if (root.val < val) {//向右树寻找
root = root.right;
}
}
//与pre做大小比较,最后将val构造的结点挂在树下
if (pre.val > val) {
pre.left = new TreeNode(val);
} else {
pre.right = new TreeNode(val);
}

return newRoot;
}
}

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) // 如果当前节点为空,也就意味着val找到了合适的位置,此时创建节点直接返回。
return new TreeNode(val);

if (root.val < val){
root.right = insertIntoBST(root.right, val); // 递归创建右子树
}else if (root.val > val){
root.left = insertIntoBST(root.left, val); // 递归创建左子树
}
return root;
}
}