Алгоритм пошуку в глибину для перевірки еквівалентності двох дерев виразів

Двійкове дерево виразів — це різновид двійкового дерева, яке використовується для представлення арифметичних виразів. Кожен вузол дерева бінарних виразів має нуль або двох дітей. Листові вузли (вузли з 0 дочірніми елементами) відповідають операндам (змінним), а внутрішні вузли (вузли з двома дочірніми елементами) відповідають операторам. У цій задачі ми розглядаємо лише оператор «+» (тобто додавання).

вираз-бінарне-дерево

Вам надано корені двох бінарних дерев виразів, root1 і root2. Повертає true, якщо два дерева бінарних виразів еквівалентні. В іншому випадку поверніть false.

Два дерева двійкових виразів є еквівалентними, якщо вони мають однакове значення, незалежно від того, які значення встановлено для змінних.

Подальші дії: що ви зміните у своєму рішенні, якщо дерево також підтримує оператор «-» (тобто віднімання)?

Приклад 1:
Вхід: корінь1 = [x], корінь2 = [x]
Вихід: істина

Приклад 2:
Вхід: корінь1 = [+,a,+,нуль,нуль,b,c], корінь2 = [+,+,b,c,a]
Вихід: істина
Пояснення: a + (b + c) == (b + c) + a

Приклад 3:
Вхід: корінь1 = [+,a,+,нуль,нуль,b,c], корінь2 = [+,+,b,d,a]
Вихід: false
Пояснення: a + (b + c) != (b + d) + a

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

Підказки:
підрахуйте для кожної змінної, скільки разів вона з’явилася в першому дереві.
Зробіть те саме для другого дерева та перевірте, чи кількість однакова для обох дерев.

Алгоритм пошуку за глибиною з хеш-таблицею

Оскільки дерево виразів є двійковим і може містити лише один символ плюса. Таким чином, ми можемо виконати алгоритм пошуку спочатку в глибину (DFS) на обох деревах бінарних виразів і підрахувати кожну змінну. Два дерева виразів є рівними, якщо обидва дерева містять однакову кількість змінних.

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

Щоб порівняти, чи рівні дві хеш-карти (unordered_map ), ми можемо просто порівняти їх у C++, використовуючи подвійний знак рівності.