二叉树

题目

给定二叉搜索树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;
    }
}