701. Insert into a Binary Search Tree

Задача

Даны корень BST и значение для вставки. Вставьте значение и верните корень BST.

Примеры

Пример 1

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]

Пояснение

Существуют и другие допустимые деревья.

Пример 2

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Пример 3

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Решение

Решение

/**
 * Time: O(h), где h — высота дерева (спускаемся по одной ветке BST).
 * Space: O(h) из-за стека рекурсии.
 *  Примечание: по условию значение val гарантированно отсутствует в дереве, поэтому кейс дубля не нужен.
 */
var insertIntoBST = function(root, val) {
    if (!root) return new TreeNode(val);
 
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
 
    return root;
};