Задача: 147. Insertion Sort List
Сложность: medium

Дана голова односвязного списка. Отсортируйте список, используя сортировку вставками, и верните голову отсортированного списка.

Шаги алгоритма сортировки вставками:

1. Сортировка вставками итеративно работает, потребляя один входной элемент за каждую итерацию и формируя отсортированный выходной список.
2. На каждой итерации сортировка вставками удаляет один элемент из входных данных, находит место, куда он принадлежит в отсортированном списке, и вставляет его туда.
3. Процесс повторяется до тех пор, пока не закончатся входные элементы.

Пример:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

👨‍💻 Алгоритм:

1⃣Создание вспомогательного узла (pseudo_head):
В качестве первого шага создайте вспомогательный узел, который называется pseudo_head. Этот узел будет использоваться как указатель на начало результирующего списка. Этот узел облегчает доступ к результирующему списку, особенно когда необходимо вставить новый элемент в начало списка. Этот прием значительно упрощает логику работы с односвязным списком.

2⃣Механизм вставки узла:
В односвязном списке каждый узел содержит только один указатель, который указывает на следующий узел. Чтобы вставить новый узел (например, B) перед определенным узлом (например, A), необходимо знать узел (например, C), который находится перед узлом A (т.е. C -> A). Имея ссылку на узел C, можно вставить новый узел так, чтобы получилось C -> B -> A.

3⃣Использование пары указателей для вставки:
Используя пару указателей (prev и next), которые служат местом для вставки нового элемента между ними, вставьте новый элемент в список. Это делается путем установки prev -> new_node -> next. Этот метод позволяет точно и безопасно вставлять новые элементы в список, сохраняя при этом правильный порядок элементов без необходимости перемещения других узлов списка.

😎 Решение:

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode curr = head;

        while (curr != null) {
            ListNode prev = dummy;

            while (prev.next != null && prev.next.val <= curr.val) {
                prev = prev.next;
            }

            ListNode next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = next;
        }

        return dummy.next;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 138. Copy List with Random Pointer
Сложность: medium

Дан связный список длиной n, в котором каждый узел содержит дополнительный случайный указатель (random pointer), который может указывать на любой узел в списке или быть равным null.

Создайте глубокую копию списка. Глубокая копия должна состоять из ровно n совершенно новых узлов, где каждый новый узел имеет значение, равное значению соответствующего оригинального узла. Указатели next и random новых узлов должны указывать на новые узлы в скопированном списке таким образом, чтобы указатели в оригинальном и скопированном списке представляли одно и то же состояние списка. Ни один из указателей в новом списке не должен указывать на узлы в оригинальном списке.

Например, если в оригинальном списке есть два узла X и Y, где X.random --> Y, то для соответствующих узлов x и y в скопированном списке, x.random должен указывать на y.

Верните голову скопированного связного списка.

Связный список представлен во входных/выходных данных как список из n узлов. Каждый узел представлен парой [val, random_index], где:
val: целое число, представляющее Node.val
random_index: индекс узла (в диапазоне от 0 до n-1), на который указывает случайный указатель, или null, если он не указывает ни на какой узел.

Вашему коду будет дана только голова оригинального связного списка.

Пример:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

👨‍💻 Алгоритм:

1⃣Инициализация и начало обхода:
Начните обход графа со стартового узла (head). Создайте словарь visited_dictionary для отслеживания посещенных и клонированных узлов.

2⃣Проверка и клонирование узлов:
Для каждого текущего узла (current_node) проверьте, есть ли уже клонированная копия в visited_dictionary.
Если клонированная копия существует, используйте ссылку на этот клонированный узел.
Если клонированной копии нет, создайте новый узел (cloned_node_for_current_node), инициализируйте его и добавьте в visited_dictionary, где ключом будет current_node, а значением — созданный клон.

3⃣Рекурсивные вызовы для обработки связей:
Сделайте два рекурсивных вызова для каждого узла: один используя указатель random, другой — указатель next.
Эти вызовы отражают обработку "детей" текущего узла в терминах графа, где детьми являются узлы, на которые указывают указатели random и next.

😎 Решение:

public class Solution {
    HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        if (this.visitedHash.containsKey(head)) {
            return this.visitedHash.get(head);
        }

        Node node = new Node(head.val, null, null);
        this.visitedHash.put(head, node);

        node.next = this.copyRandomList(head.next);
        node.random = this.copyRandomList(head.random);

        return node;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 94. Binary Tree Inorder Traversal
Сложность: easy

Дан корень бинарного дерева. Верните обход значений его узлов в симметричном порядке.

Пример:

Input: root = [1,null,2,3]
Output: [1,3,2]

👨‍💻 Алгоритм:

1⃣Создаём вспомогательную функцию helper, которая будет рекурсивно обходить дерево.

2⃣В каждом узле сначала рекурсивно вызываем helper для левого поддерева.

3⃣После левого поддерева добавляем значение текущего узла в список, затем переходим к правому поддереву.

😎 Решение:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public void helper(TreeNode root, List<Integer> res) {
        if (root != null) {
            helper(root.left, res);
            res.add(root.val);
            helper(root.right, res);
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: №26. Remove Duplicates from Sorted Array
Сложность: easy

Дан целочисленный массив nums, отсортированный в неубывающем порядке.
Удалите дубликаты *на месте*, чтобы каждый уникальный элемент встречался только один раз.
Порядок должен сохраняться, и нужно вернуть количество уникальных элементов k.

Пример:

Input: nums = [1,1,2] Output: 2 (nums = [1,2,_])

👨‍💻 Алгоритм:

1⃣Если длина массива ≤ 1 — вернуть её как результат, дубликатов нет.

2⃣Используем два указателя:
- left — указывает на последний уникальный элемент;
- right — проходит по массиву, сравнивая текущий элемент с nums[left].

3⃣Если найден уникальный элемент — перемещаем его на позицию left + 1, увеличиваем оба указателя.

😎 Решение:

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 1) return n;

        int left = 0;
        int right = 1;

        while (right < n) {
            if (nums[right] != nums[left]) {
                nums[left + 1] = nums[right];
                left++;
            }
            right++;
        }

        return left + 1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

🚨 60 минут до финала

Через час мы закроем краудфандинг easyoffer 2.0
Это последний шанс вписаться в самые выгодные условия.

👉 https://planeta.ru/campaigns/easyoffer

Задача: 160. Intersection of Two Linked Lists
Сложность: easy

Даны головы двух односвязных списков headA и headB. Верните узел, в котором эти два списка пересекаются. Если два связанных списка не имеют пересечений, верните null.

Например, следующие два связанных списка начинают пересекаться в узле c1.

Пример:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

👨‍💻 Алгоритм:

1⃣Сохранение ссылок из списка B:
Проходим по всем узлам списка B и сохраняем ссылки (адреса) каждого узла в хеш-таблицу. Это позволит нам быстро проверять, содержится ли узел из списка A в списке B.

2⃣Проверка узлов списка A:
Далее, для каждого узла из списка A проверяем, существует ли такой узел в хеш-таблице, созданной на предыдущем шаге. Если такой узел найден, то он является точкой пересечения, и мы возвращаем этот узел.

3⃣Обработка отсутствия пересечения:
Если до конца списка A не найдено ни одного узла, который бы совпал с узлами из хеш-таблицы, возвращаем null, указывая на отсутствие пересечения между списками.

😎 Решение:

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> nodesInB = new HashSet<ListNode>();

        while (headB != null) {
            nodesInB.add(headB);
            headB = headB.next;
        }

        while (headA != null) {
            if (nodesInB.contains(headA)) {
                return headA;
            }
            headA = headA.next;
        }

        return null;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

Гарантируется, что каждый город может добраться до города 0 после перенаправления.

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

👨‍💻 Алгоритм:

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

class Solution {
    int count = 0;

    public void dfs(int node, int parent, Map<Integer, List<List<Integer>>> adj) {
        if (!adj.containsKey(node)) {
            return;
        }
        for (List<Integer> nei : adj.get(node)) {
            int neighbor = nei.get(0);
            int sign = nei.get(1);
            if (neighbor != parent) {
                count += sign;
                dfs(neighbor, node, adj);
            }
        }
    }

    public int minReorder(int n, int[][] connections) {
        Map<Integer, List<List<Integer>>> adj = new HashMap<>();
        for (int[] connection : connections) {
            adj.computeIfAbsent(connection[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(connection[1], 1));
            adj.computeIfAbsent(connection[1], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(connection[0], 0));
        }
        dfs(0, -1, adj);
        return count;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 303. Range Sum Query - Immutable
Сложность: easy

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

👨‍💻 Алгоритм:

1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

public class NumArray {
    private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 95. Unique Binary Search Trees II
Сложность: medium

Дано целое число n. Верните все структурно уникальные деревья бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n. Ответ может быть представлен в любом порядке.

Пример:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

👨‍💻 Алгоритм:

1⃣Создайте хеш-карту memo, где memo[(start, end)] содержит список корневых узлов всех возможных BST (деревьев бинарного поиска) с диапазоном значений узлов от start до end. Реализуем рекурсивную функцию allPossibleBST, которая принимает начальный диапазон значений узлов start, конечный диапазон end и memo в качестве параметров. Она возвращает список TreeNode, соответствующих всем BST, которые могут быть сформированы с этим диапазоном значений узлов. Вызываем allPossibleBST(1, n, memo) и выполняем следующее:

2⃣Объявляем список TreeNode под названием res для хранения списка корневых узлов всех возможных BST. Если start > end, мы добавляем null в res и возвращаем его. Если мы уже решили эту подзадачу, т.е. memo содержит пару (start, end), мы возвращаем memo[(start, end)].

3⃣Выбираем значение корневого узла от i = start до end, увеличивая i на 1 после каждой итерации. Рекурсивно вызываем leftSubtrees = allPossibleBST(start, i - 1, memo) и rightSubTrees = allPossibleBST(i + 1, end, memo). Перебираем все пары между leftSubtrees и rightSubTrees и создаем новый корень со значением i для каждой пары. Добавляем корень новообразованного BST в res. Устанавливаем memo[(start, end)] = res и возвращаем res.

😎 Решение:

class Solution {
    public List<TreeNode> allPossibleBST(
        int start,
        int end,
        Map<Pair<Integer, Integer>, List<TreeNode>> memo
    ) {
        List<TreeNode> res = new ArrayList<>();
        if (start > end) {
            res.add(null);
            return res;
        }
        if (memo.containsKey(new Pair<>(start, end))) {
            return memo.get(new Pair<>(start, end));
        }
        for (int i = start; i <= end; ++i) {
            List<TreeNode> leftSubTrees = allPossibleBST(start, i - 1, memo);
            List<TreeNode> rightSubTrees = allPossibleBST(i + 1, end, memo);
            for (TreeNode left : leftSubTrees) {
                for (TreeNode right : rightSubTrees) {
                    TreeNode root = new TreeNode(i, left, right);
                    res.add(root);
                }
            }
        }
        memo.put(new Pair<>(start, end), res);
        return res;
    }

    public List<TreeNode> generateTrees(int n) {
        Map<Pair<Integer, Integer>, List<TreeNode>> memo = new HashMap<>();
        return allPossibleBST(1, n, memo);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 900. RLE Iterator
Сложность: medium

Для кодирования последовательности целых чисел мы можем использовать кодирование по длине строки (т. е. RLE). В кодированном по длине пробега массиве четной длины (с индексацией 0) для всех четных i значение encoding[i] говорит нам о том, сколько раз неотрицательное целое значение encoding[i + 1] повторяется в последовательности.

Например, последовательность arr = [8,8,8,5,5] может быть закодирована как encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] и encoding = [2,8,1,8,2,5] также являются допустимыми RLE для arr.
Задав кодированный по длине пробега массив, разработайте итератор для его итерации. Реализуйте класс RLEIterator: RLEIterator(int[] encoded) Инициализирует объект с кодированным массивом encoded. int next(int n) Исчерпывает следующие n элементов и возвращает последний исчерпанный таким образом элемент. Если не осталось элементов для исчерпания, возвращает -1.

Пример:

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

👨‍💻 Алгоритм:

1⃣Инициализировать итератор с закодированным массивом и индексом, указывающим на текущую позицию.

2⃣При вызове метода next(n), уменьшить текущий счетчик на n или перейти к следующему числу, если текущий счетчик равен нулю.

3⃣Возвращать текущий элемент или -1, если все элементы исчерпаны.

😎 Решение:

class RLEIterator {
    private int[] encoding;
    private int index;

    public RLEIterator(int[] encoding) {
        this.encoding = encoding;
        this.index = 0;
    }

    public int next(int n) {
        while (index < encoding.length) {
            if (n > encoding[index]) {
                n -= encoding[index];
                index += 2;
            } else {
                encoding[index] -= n;
                return encoding[index + 1];
            }
        }
        return -1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 830. Positions of Large Groups
Сложность: easy

В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа.
Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy".
Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6].
Группа считается большой, если в ней 3 или более символов.

Верните интервалы каждой большой группы, отсортированные в порядке возрастания начального индекса.

Пример:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

👨‍💻 Алгоритм:

1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы.

2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат.

3⃣Обновите i = j + 1 и начните новую группу.

😎 Решение:

class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> ans = new ArrayList();
        int i = 0, N = S.length();
        for (int j = 0; j < N; ++j) {
            if (j == N-1 || S.charAt(j) != S.charAt(j+1)) {
                if (j-i+1 >= 3)
                    ans.add(Arrays.asList(new Integer[]{i, j}));
                i = j + 1;
            }
        }

        return ans;
    }

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1134. Armstrong Number
Сложность: easy

Дано целое число n, верните true, если и только если оно является числом Армстронга.

k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n.

Пример:

Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3.

👨‍💻 Алгоритм:

1⃣Получите количество цифр в n, преобразовав его в строку и найдя длину.

2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n.
Инициализируйте переменную result для хранения результата.
Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру.

3⃣Верните true, если результат равен исходному числу n.

😎 Решение:

class Solution {
    public int getSumOfKthPowerOfDigits(int n, int k) {
       int result = 0;

       while (n != 0) {
           result += Math.pow(n % 10, k);

           n /= 10;
       }
       return result;
    }
    public boolean isArmstrong(int n) {
        int length = String.valueOf(n).length();

        return getSumOfKthPowerOfDigits(n, length) == n;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1016. Binary String With Substrings Representing 1 To N
Сложность: medium

Если задана двоичная строка s и положительное целое число n, верните true, если двоичное представление всех целых чисел в диапазоне [1, n] является подстрокой s, или false в противном случае. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "0110", n = 3
Output: true

👨‍💻 Алгоритм:

1⃣Генерация двоичных строк:
Для каждого числа в диапазоне [1, n] сгенерируйте его двоичное представление.

2⃣Проверка подстрок:
Проверьте, является ли каждое из двоичных представлений подстрокой строки s.

3⃣Возврат результата:
Если все двоичные представления являются подстроками строки s, верните true. В противном случае, верните false.

😎 Решение:

public class Solution {
    public boolean queryString(String s, int n) {
        for (int i = 1; i <= n; i++) {
            String binary = Integer.toBinaryString(i);
            if (!s.contains(binary)) {
                return false;
            }
        }
        return true;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 747. Largest Number At Least Twice of Others
Сложность: easy

Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1.

Пример:

Input: nums = [3,6,1,0]
Output: 1

👨‍💻 Алгоритм:

1⃣Найдите максимальный элемент в массиве и его индекс.

2⃣Проверьте, является ли этот максимальный элемент по крайней мере в два раза больше всех остальных элементов массива.

3⃣Если условие выполняется, верните индекс максимального элемента, иначе верните -1.

😎 Решение:

public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
        }
        return Math.min(dp[n - 1], dp[n - 2]);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 236. Lowest Common Ancestor of a Binary Tree
Сложность: medium

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

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

👨‍💻 Алгоритм:

1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях.

2⃣Проверка поддеревьев: Выполните рекурсивный обход левой и правой ветвей дерева. Если какая-либо из ветвей (левая или правая) возвращает True, это означает, что один из двух узлов найден ниже по дереву.

3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q.

😎 Решение:

class Solution {
    private TreeNode ans;

    public Solution() {
        this.ans = null;
    }

    private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {
        if (currentNode == null) {
            return false;
        }

        int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;
        int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;
        int mid = (currentNode == p || currentNode == q) ? 1 : 0;

        if (mid + left + right >= 2) {
            this.ans = currentNode;
        }

        return (mid + left + right > 0);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.recurseTree(root, p, q);
        return this.ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний