Алгоритм поиска в глубину для проверки эквивалентности двух деревьев выражений

Бинарное дерево выражений — это своего рода бинарное дерево, используемое для представления арифметических выражений. Каждый узел бинарного дерева выражений имеет ноль или двух потомков. Листовые узлы (узлы с 0 дочерними элементами) соответствуют операндам (переменным), а внутренние узлы (узлы с двумя дочерними элементами) соответствуют операторам. В этой задаче мы рассматриваем только оператор ‘+’ (т.е. сложение).

бинарное дерево выражений

Вам даны корни двух бинарных деревьев выражений, root1 и root2. Возвращает true, если два дерева бинарных выражений эквивалентны. В противном случае вернуть ложь.

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

Дополнение: что вы измените в своем решении, если дерево также поддерживает оператор «-» (т. е. вычитание)?

Пример 1:
Ввод: root1 = [x], root2 = [x]
Вывод: true

Пример 2:
Ввод: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Вывод: true
Объяснение: a + (b + c) == (б + в) + а

Пример 3:
Ввод: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Вывод: false
Объяснение: a + (b + c) != (б + г) + а

Ограничения:
количество узлов в обоих деревьях равно, нечетно и находится в диапазоне [1, 4999].
Node.val — это «+» или строчная английская буква.
Гарантируется, что заданное дерево является допустимым деревом бинарных выражений.

Подсказки:
посчитайте для каждой переменной, сколько раз она появлялась в первом дереве.
Сделайте то же самое для второго дерева и проверьте, одинаково ли количество для обоих деревьев.

Алгоритм поиска в глубину с хэш-таблицей

Поскольку дерево выражений является бинарным и может содержать только один символ плюса. Следовательно, мы можем выполнить алгоритм поиска в глубину (DFS) для обоих деревьев бинарных выражений и подсчитать каждую переменную. Два дерева выражений равны, если оба дерева содержат одинаковое количество переменных.

DFS выполняется за время O(N), где N — количество узлов в обоих бинарных деревьях выражений. Сложность пространства составляет O (N), поскольку мы используем стек через рекурсию, а также необходимо записывать счетчики для каждой переменной.

Чтобы сравнить, равны ли две хеш-карты (unordered_map ), мы можем просто сравнить их в C++, используя двойной знак равенства.