Задача: 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 var ans: TreeNode?

    init() {
        self.ans = nil
    }

    private func recurseTree(_ currentNode: TreeNode?, _ p: TreeNode, _ q: TreeNode) -> Bool {
        guard let currentNode = currentNode else { return false }

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

        if mid + left + right >= 2 {
            self.ans = currentNode
        }

        return (mid + left + right > 0)
    }

    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode, _ q: TreeNode) -> TreeNode? {
        _ = recurseTree(root, p, q)
        return self.ans
    }
}

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