Условие

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

Примеры

Input: root = [1,1,1,1,1,null,1] Output: true

Input: root = [2,2,2,5,2] 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 isUnivalTree(root: TreeNode?): Boolean {
    // Если дерево пустое, оно считается однозначным
    if (root == null) return true

    // Проверяем левый поддерево
    if (root.left != null && root.left?.`val` != root.`val`) return false

    // Проверяем правый поддерево
    if (root.right != null && root.right?.`val` != root.`val`) return false

    // Рекурсивно проверяем левое и правое поддеревья
    return isUnivalTree(root.left) && isUnivalTree(root.right)
}

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

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

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

O(h), где h — высота дерева, что связано с глубиной рекурсии на стеке вызовов.