Cây con đảo ngược (Inverted Subtree) trong C++

Cho 2 cây nhị phân source và target. Kiểm tra có tồn tại một phép đảo ngược (inversion) của source là cây con của target không. Cây đảo ngược: có thể hoán đổi trái/phải tại bất kỳ nút nào.

Thuật toán

• Hàm check(n1,n2): kiểm tra n1 và n2 là đảo ngược nhau (đệ quy: so sánh trái-trái & phải-phải HOẶC trái-phải & phải-trái).
• Hàm solve(source,target): duyệt target, tại mỗi nút gọi check với source.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val; TreeNode *left, *right;
    TreeNode(int d) : val(d), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool check(TreeNode* n1, TreeNode* n2) {
        if (!n1 && !n2) return true;
        if (!n1 || !n2) return false;
        if (n1->val != n2->val) return false;
        bool op1 = check(n1->left, n2->left) && check(n1->right, n2->right);
        bool op2 = check(n1->right, n2->left) && check(n1->left, n2->right);
        return op1 || op2;
    }
    bool solve(TreeNode* source, TreeNode* target) {
        if (!source && !target) return true;
        if (!source || !target) return false;
        if (check(target, source)) return true;
        return solve(source, target->left) || solve(source, target->right);
    }
};

int main() {
    Solution ob;
    TreeNode* target = new TreeNode(6);
    target->left = new TreeNode(3);
    target->right = new TreeNode(1);
    target->right->left = new TreeNode(3);
    target->right->right = new TreeNode(2);
    target->right->right->left = new TreeNode(4);
    TreeNode* source = new TreeNode(1);
    source->left = new TreeNode(2);
    source->right = new TreeNode(3);
    source->left->right = new TreeNode(4);
    cout << ob.solve(source, target);
    return 0;
}

Đầu ra

1