Условие

Дано корневое дерево с уникальными значениями и два различных целых числа x и y. Требуется определить, являются ли узлы с этими значениями двоюродными. В бинарном дереве два узла считаются двоюродными, если они находятся на одном уровне (глубине) и имеют разных родителей.

Примеры

Input: root = [1,2,3,4], x = 4, y = 3 Output: false

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4 Output: true

Input: root = [1,2,3,null,4], x = 2, y = 3 Output: false

Решение

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
 fun isCousins(root: TreeNode?, x: Int, y: Int): Boolean {
    // Если дерево пустое, возвращаем false
    if (root == null) return false

    // Инициализируем очередь для обхода в ширину
    val queue: Queue<TreeNode> = LinkedList()
    queue.add(root)

    // Начинаем обход по уровням
    while (queue.isNotEmpty()) {
        var xFound = false
        var yFound = false
        val size = queue.size

        for (i in 0 until size) {
            val node = queue.poll()

            // Проверяем, является ли текущий узел родителем x и y
            if (node.left != null && node.right != null) {
                if ((node.left!!.`val` == x && node.right!!.`val` == y) ||
                    (node.left!!.`val` == y && node.right!!.`val` == x)) {
                    return false
                }
            }

            // Проверяем, найден ли x или y на текущем уровне
            if (node.`val` == x) xFound = true
            if (node.`val` == y) yFound = true

            // Добавляем дочерние узлы в очередь для следующего уровня
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }

        // Если x и y найдены на одном уровне, но не являются братьями, возвращаем true
        if (xFound && yFound) return true
        // Если только один из них найден на текущем уровне, возвращаем false
        if (xFound || yFound) return false
    }

    return false
}

Временная сложность

O(n), где n — количество узлов в дереве, поскольку мы можем посетить каждый узел один раз.

Пространственная сложность

O(w), где w — максимальная ширина дерева, так как очередь может содержать до w узлов на самом широком уровне.