// Даны 2 ноды нужно найти их ближайшего общего предка

// мы будем использовать рекурсивный обход дерева, чтобы найти путь от корня до каждого из узлов, а затем сравним эти пути, чтобы найти последний общий элемент

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

// Функция для поиска пути от корня до заданного узла
func findPath(_ root: TreeNode?, _ node: TreeNode, _ path: inout [TreeNode]) -> Bool {
    if root == nil {
        return false
    }

    // Добавляем текущий узел в путь
    path.append(root!)

    // Если текущий узел - целевой узел, возвращаем true
    if root === node {
        return true
    }

    // Проверяем, присутствует ли целевой узел в левом или правом поддереве
    if findPath(root?.left, node, &path) || findPath(root?.right, node, &path) {
        return true
    }

    // Если целевой узел не найден в поддереве, удаляем текущий узел из пути и возвращаем false
    path.removeLast()
    return false
}

// Функция для нахождения ближайшего общего предка
func closestCommonAncestor(_ root: TreeNode?, _ p: TreeNode, _ q: TreeNode) -> TreeNode? {
    var pathP = [TreeNode]()
    var pathQ = [TreeNode]()

    // Находим пути от корня до узлов p и q
    guard findPath(root, p, &pathP) && findPath(root, q, &pathQ) else {
        return nil
    }

    // Сравниваем пути для нахождения последнего общего узла
    var i = 0
    while i < pathP.count && i < pathQ.count && pathP[i] === pathQ[i] {
        i += 1
    }

    // Возвращаем последний общий узел
    return i > 0 ? pathP[i - 1] : nil
}







// Пример использования:
// Создаем бинарное дерево
let root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left?.left = TreeNode(6)
root.left?.right = TreeNode(2)
root.left?.right?.left = TreeNode(7)
root.left?.right?.right = TreeNode(4)
root.right?.left = TreeNode(0)
root.right?.right = TreeNode(8)

let p = root.left?.left // Узел со значением 6
let q = root.left?.right?.right // Узел со значением 4

// Находим ближайшего общего предка
if let ancestor = closestCommonAncestor(root, p!, q!) {
    print("Ближайший общий предок:", ancestor.val)
} else {
    print("Общий предок не найден.")
}