給定二叉搜索樹(shù)（BST）的根節(jié)點(diǎn) root 和要插入樹(shù)中的值 value ，將值插入二叉搜索樹(shù)。 返回插入后二叉搜索樹(shù)的根節(jié)點(diǎn)。新值和原始二叉搜索樹(shù)中的任意節(jié)點(diǎn)值都不同。

注意，可能存在多種有效的插入方式，只要樹(shù)在插入后仍保持為二叉搜索樹(shù)即可。 你可以返回任意有效的結(jié)果 。

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

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

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

image.png

另一個(gè)滿足題目要求可以通過(guò)的樹(shù)是：

image.png

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) { // 直接插入
            return new TreeNode(val);
        }
        TreeNode cur = root;
        while (cur != null) {
            if (val < cur.val) {
                if (cur.left == null) { // 插入到left
                    cur.left = new TreeNode(val);
                    break;
                } else {
                    cur = cur.left;
                }
            } else {
                if (cur.right == null) { // 插入到right
                    cur.right = new TreeNode(val);
                    break;
                } else {
                    cur = cur.right;
                }
            }
        }
        return root;
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(N)，其中 N 為樹(shù)中節(jié)點(diǎn)的數(shù)目。最壞情況下，我們需要將值插入到樹(shù)的最深的葉子結(jié)點(diǎn)上，而葉子節(jié)點(diǎn)最深為 O(N)。
• 空間復(fù)雜度：O(1)。我們只使用了常數(shù)大小的空間。