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

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

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

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

示例:

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和 插入的值: 5
你可以返回这个二叉搜索树:

         4
       /   \
      2     7
     / \   /
    1   3 5
或者这个树也是有效的:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 创建二叉树

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

• 1. 递归法

思路：

1. 递归终止条件为当前节点为空，创建一个新的节点即可
2. 判断要插入的值 val 和根节点的大小，如果 val < root.val，则插入左子树
3. 如果 val > root.val，则插入右子树

public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (val < root.val) root.left =  insertIntoBST(root.left, val);
        else if (val > root.val) root.right =  insertIntoBST(root.right, val);
        return root;
    }

复杂度分析：

• 时间复杂度：O(log(n)), 一般情况下插入操作是O(log(n)), 但当二叉搜索树退化成链表是，复杂度为O(n)
• 空间复杂度：O(log(n)), 递归深度 O(log(n))

---

• 源码

• 我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github