Задача: 993. Cousins in Binary Tree
Сложность: easy

Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.

Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.

Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.

Пример:

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

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

1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.

2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.

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

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    private var parentX: TreeNode? = null
    private var parentY: TreeNode? = null
    private var depthX = -1
    private var depthY = -1
    
    fun isCousins(root: TreeNode?, x: Int, y: Int): Boolean {
        dfs(root, null, 0, x, y)
        return depthX == depthY && parentX != parentY
    }
    
    private fun dfs(node: TreeNode?, parent: TreeNode?, depth: Int, x: Int, y: Int) {
        if (node == null) return
        if (node.`val` == x) {
            parentX = parent
            depthX = depth
        } else if (node.`val` == y) {
            parentY = parent
            depthY = depth
        } else {
            dfs(node.left, node, depth + 1, x, y)
            dfs(node.right, node, depth + 1, x, y)
        }
    }
}

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