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

Двійкове дерево виразів — це різновид двійкового дерева, яке використовується для представлення арифметичних виразів. Кожен вузол дерева бінарних виразів має нуль або двох дітей. Листові вузли (вузли з 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) на обох деревах бінарних виразів і підрахувати кожну змінну. Два дерева виразів є рівними, якщо обидва дерева містять однакову кількість змінних.

/**
 * Definition for a binary tree node.
 * struct Node {
 *     char val;
 *     Node *left;
 *     Node *right;
 *     Node(): val(' '), left(nullptr), right(nullptr) {}
 *     Node(char x): val(x), left(nullptr), right(nullptr) {}
 *     Node(char x, Node *left, Node *right): val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool checkEquivalence(Node* root1, Node* root2) {
        if (root1 == root2) return true;
        unordered_map<char, int> count1, count2;
        dfs(root1, count1);
        dfs(root2, count2);
        return count1 == count2;
    }
    
private:        
    void dfs(Node* root, unordered_map<char, int> &count) {
        if (!root) return ;
        if (root->val != '+') count[root->val] ++;
        dfs(root->left, count);
        dfs(root->right, count);
    }
};

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

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