Задача: 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?
    var right: TreeNode?
    
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

class Solution {
    var parentX: TreeNode?
    var parentY: TreeNode?
    var depthX = -1
    var depthY = -1
    
    func isCousins(_ root: TreeNode?, _ x: Int, _ y: Int) -> Bool {
        func dfs(_ node: TreeNode?, _ parent: TreeNode?, _ depth: Int) {
            guard let node = node else { 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)
                dfs(node.right, node, depth + 1)
            }
        }
        
        dfs(root, nil, 0)
        return depthX == depthY && parentX !== parentY
    }
}

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