Same Tree

Лёгкая№100узлы дерева

Даны корни двух двоичных деревьев, p и q. Нужно сказать, одинаковы ли они: та же форма и то же значение в каждом соответствующем месте. Наши деревья: оба — 5 с потомками 8 и 6; в p у 6 левый потомок 4, в q у 6 правый потомок 4 — ответ false: значения те же, но 4 висит с разных сторон.

100 Same TreeРазбор · 1×

Пример: проверить, одинаковы ли два двоичных дерева: идём по обоим сразу и сравниваем их место за местом.

pqnonenonenonenonenone5864nonenonenonenonenone5864стек вызовов isSame, вершина справаp5q5
ещё не сравнивалипара ждёт в стеке вызововпара, которую сравниваемпара вернула trueпара вернула falsenone: пустой потомок

p — 5, q — 5: не оба none

01/27
сначала · назад · пуск · шаг
Скорость
1function isSame(p, q):
2 if p is none and q is none:
3 return true
4 if p is none or q is none:
5 return false
6 if p.val != q.val:
7 return false
8 if not isSame(p.left, q.left):
9 return false
10 return isSame(p.right, q.right)
состояние
p
5
q
5
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Деревья одинаковы ровно тогда, когда равны корни, одинаковы левые поддеревья и одинаковы правые, поэтому isSame отвечает за пару узлов по ответам для пар их потомков.
  2. Пустой потомок должен встретиться с пустым: здесь все значения совпадают, и только пара (4, none) под 6 показывает, что форма разная.
  3. Первый false сразу поднимается через все вызовы, поэтому остаток обоих деревьев не сравниваем.

Сложность

Время O(n), где n — размер меньшего дерева: каждую пару мест сравниваем не больше одного раза. Память O(h), где h — его высота: в стеке вызовов лежит один путь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.