701-二叉搜索树中的插入操作

题目地址(701. 二叉搜索树中的插入操作 - 力扣（LeetCode）)

https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

题目描述

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

思路

存在多种插入方式，在插入到叶子节点的方式是最简单的。

利用二叉搜索树的特性，可以将节点插入对应的叶子节点中。

递归函数定义：

public TreeNode insertIntoBST(TreeNode root, int val)

递归终止条件：当 root 为空，直接返回新节点

递归逻辑：

1. 如果 val 大于 root 节点，就往右子树搜索
2. 如果 val 小于 root 节点，就往左子树搜索
3. 最后返回root

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);
        if(root.val < val){
            root.right = insertIntoBST(root.right,val);
        }
        if(root.val > val){
            root.left = insertIntoBST(root.left,val);
        }
        return root;

    }
}

复杂度分析

令 n 为二叉树节点个数。

• 时间复杂度：$O(n)$,最坏情况下，我们需要将值插入到树的最深的叶子结点上，而叶子节点最深为 O(N)。
• 空间复杂度：$O(n)$，最坏情况下，需要栈空间深度为 O(n)

迭代写法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        TreeNode newRoot = root;
        TreeNode prev = root;
        while (root != null) {
            prev = root;
            // 找到叶子节点
            if (root.val > val) {
                root = root.left;
            } else if (root.val < val) {
                root = root.right;
            }
        }
        // 放进去
        if (prev.val > val) {
            prev.left = new TreeNode(val);
        } else {
            prev.right = new TreeNode(val);
        }
        return newRoot;
    }
}