235. Lowest Common Ancestor of a Binary Search Tree

Задача

Дан BST и два узла. Найдите их наименьшего общего предка (LCA).

Примеры

Пример 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6

Пояснение

LCA узлов 2 и 8 — это 6.

Пример 2

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2

Пояснение

LCA узлов 2 и 4 — это 2, так как узел может быть предком самого себя.

Пример 3

Input: root = [2,1], p = 2, q = 1
Output: 2

Решение

Решение

/**
 * Временная сложность: O(h), где h - высота дерева
 * В худшем случае (несбалансированное): O(n)
 * В лучшем случае (сбалансированное): O(log n)
 * 
 * Пространственная сложность: O(1)
 */
var lowestCommonAncestor = function(root, p, q) {
    while (root) {
        // Если оба узла меньше текущего - идем влево
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        }
        // Если оба узла больше текущего - идем вправо
        else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        }
        // Иначе нашли LCA
        else {
            return root;
        }
    }
    return root;
};