Same Tree

Условие

Даны корни 2 бинарных деревьев p и q. Напишите функцию, которая проверит, являются ли они одинаковыми или нет. Два бинарных дерева считаются одинаковыми, если они структурно идентичны, а узлы имеют одинаковое значение.

Примеры

Input: p = [1, 2, 3], q = [1, 2, 3]

Output: true

Input: p = [1, 2], q = [1, null, 2]

Output: false

Input: p = [1, 2, 1], q = [1, 1, 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 isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
    if (p == null && q == null) return true // оба дерева пустые
    if (p == null || q == null) return false // одно дерево пустое
    return p.`val` == q.`val` && isSameTree(p.left, q.left) && isSameTree(p.right, q.right) // сравнение значений и рекурсивный вызов
}

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

O(n), где n — количество узлов в дереве.

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

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