Cây nhị phân tương đương lật ngược trong C++

Cho hai cây nhị phân. Lật ngược (flip) một cây nghĩa là chọn một nút bất kỳ và hoán đổi cây con trái và phải của nó. Cây X tương đương lật ngược với cây Y nếu có thể biến X thành Y sau một số phép lật. Viết hàm xác định hai cây có tương đương lật ngược hay không. Ví dụ: lật các nút giá trị 1, 3, 5 sẽ làm cho hai cây giống nhau → trả về true.

Giải thuật

• Định nghĩa hàm đệ quy solve(t1, t2):
  • Nếu cả hai null → true.
  • Nếu một null → false.
  • Nếu t1->val != t2->val → false.
  • Nếu (cả hai không có con trái) HOẶC (cả hai có con trái VÀ giá trị con trái bằng nhau):
    • Trả về solve(t1->left, t2->left) && solve(t1->right, t2->right).
  • Ngược lại:
    • Trả về solve(t1->left, t2->right) && solve(t1->right, t2->left).

Ví dụ mã C++

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = NULL; right = NULL; }
};

class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) return true;
        if (!root1 || !root2) return false;
        if (root1->val != root2->val) return false;
        if ((!root1->left && !root2->left) ||
            (root1->left && root2->left && root1->left->val == root2->left->val)) {
            return flipEquiv(root1->left, root2->left) &&
                   flipEquiv(root1->right, root2->right);
        } else {
            return flipEquiv(root1->left, root2->right) &&
                   flipEquiv(root1->right, root2->left);
        }
    }
};

Đầu vào

[1,2,3,4,5,6,null,null,null,7,8] [1,3,2,null,6,4,5,null,null,null,null,8,7]

Đầu ra

1