100. То же дерево 🚀

Вопрос

В этой статье мы рассмотрим 100. То же дерево. Этот вопрос оценивается как простой вопрос.

Вопрос:

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

Пример:

     1      1
    / \    / \
   2   3  2   3

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

Объяснение вопроса

Нас просят проверить, являются ли два бинарных дерева одинаковыми или нет. Это означает, что мы должны сравнивать все значения nodes из обоих деревьев в одном и том же порядке.

Что мы знаем?

Что у нас есть 2 дерева и нам нужно проверить, что они одинаковые
Максимальное количество узлов, которое может иметь дерево, равно 100.

Как мы собираемся это сделать:

Мы собираемся сделать это рекурсивно. Это означает, что каждый узел в обоих деревьях мы будем посещать в одной точке. Мы делаем это, вызывая функцию isSameTree с указателями left или right.
Мы собираемся перейти к каждому узлу в обоих деревьях в одно и то же время. То есть в дереве 1, когда мы идем налево, мы также идем налево в дереве 2. Пока не достигнем самого конца этого правого дерева. Мы также проделаем это с правым деревом.
Каждый раз, когда мы посещаем новую ноду, мы будем делать проверку, обе ноды пусты? В этом случае оба дерева пусты и находятся в конце, а значит, правильны.
Есть ли какие-либо указатели null, которые не должны быть? Это означает, что зеркальный узел не является нулевым? В данном случае это недопустимое дерево.
Затем мы проверяем значения. Разве они не одинаковы? Тогда это недопустимое дерево
Повторяйте это до тех пор, пока все узлы не будут исчерпаны, сравнивая, что и левое, и правое деревья действительны.

Обозначение большого O:

Временная сложность: O(n) | Где n равно количеству узлов в обоих деревьях. | Мы посещаем каждый узел в худшем случае
Сложность пространства: O(h) | Где h – высота самого высокого дерева. Это находится в стеке вызовов | В худшем случае количество узлов дерева — это его высота. Таким образом, утверждается, что реальная сложность пространства составляет O(n)

Результаты литкода:

Смотрите ссылку на отправку:

Время выполнения: 64 мс, быстрее, чем 84,15% онлайн-отправок JavaScript для Same Tree.
Использование памяти: 42,3 МБ, менее чем 58,35% онлайн-предложений JavaScript для Same Tree.

Решение

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val   = (val===undefined ? 0 : val)
 * this.left  = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    
    // So both our trees current node is null
    // This mean's they both reached the end of the tree
    // at the same time without error
    if (p == null && q == null) {
        return true;
    }
    // One of the pointers are null when another is not
    // This mean's one of our pointers has traversed to a correct node
    // but another has reached the end of the list too early and thus
    // cannot be a valid mirror tree
    if ((p == null && q != null) || (q == null && p != null)) {
        return false;
    }
    // As we have moved nodes
    // Are they the same value?
    if (p.val != q.val) {
        return false;
    }
    // Get both left nodes
    // We will traverse the left nodes in a DFS fashion
    // to be able to compare both left nodes at the same time
    // So we move left at the same time on both trees.
    let good_lefts = isSameTree(p.left, q.left);
    // Get both right nodes
    // We will traverse the right nodes in a DFS fashion
    // to be able to compare both right nodes at the same time
    // So we move right at the same time on both trees.
    let good_rights = isSameTree(p.right, q.right);
    // So are both sides good?
    return good_lefts && good_rights;
};