Условие

Даны два бинарных дерева root и subRoot. Требуется определить, является ли дерево subRoot поддеревом дерева root. Дерево subRoot считается поддеревом дерева root, если существует узел в дереве root, начиная с которого все узлы совпадают с узлами дерева subRoot.

Примеры

Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2] Output: true

Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 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 isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
    // Локальная вспомогательная функция для проверки совпадения двух деревьев
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        // Если оба дерева пустые, они совпадают
        if (p == null && q == null) return true

        // Если одно из деревьев пустое, а другое нет, они не совпадают
        if (p == null || q == null) return false

        // Если значения текущих узлов не совпадают, деревья не совпадают
        if (p.`val` != q.`val`) return false

        // Проверяем совпадение левых и правых поддеревьев
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }

    // Если поддерево пустое, то оно является поддеревом любого дерева
    if (subRoot == null) return true

    // Если дерево пустое, то поддерева быть не может
    if (root == null) return false

    // Проверяем, совпадают ли текущие деревья
    if (isSameTree(root, subRoot)) return true

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

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

O(n * m) — Для каждого узла дерева root вызываем проверку совпадения с деревом subRoot, где n — количество узлов в root, m — количество узлов в subRoot.

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

O(h) — Используется стек рекурсии, где h — максимальная высота дерева (в среднем O(log n), в худшем случае O(n)).