Идентичность деревьев

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

Два бинарных дерева считаются одинаковыми, если они структурно идентичны, а узлы имеют одинаковое значение.

Пример №1

Ввод: p = [1,2,3], q = [1,2,3]
Вывод: true

Пример №2

Ввод: p = [1,2], q = [1,null,2]
Вывод: false

Пример №3

Ввод: p = [1,2,1], q = [1,1,2]
Вывод: false

Решение

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

В коде решения для сравнения двух узлов используется три проверки:

1. Если оба узла null, то они идентичны, поэтому возвращаем true (строка 15).
2. Если один из узлов null, а другой нет, то они не идентичны, поэтому возвращаем false (строка 18).
3. Если оба узла не null, то проверяем, равны ли они по значению (строка 21).

Если узлы равны по значению, то рекурсивно вызываем функцию isSameTree для левого и правого поддеревьев (строка 24).

Если же хотя бы одна из проверок не пройдена, то функция возвращает false.

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

Код решения в виде текста

/**
 * Определение узла бинарного дерева.
 * 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}
 */
const isSameTree = (p, q) => {
  if (!p && !q) { // оба узла null
    return true;
  }
  if (!p || !q) { // один из узлов null
    return false;
  }
  if (p.val !== q.val) { // узлы имеют разные значения
    return false;
  }
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

Больше интересных разборов в канале @js_is_easy, подписывайся