Cây đối xứng (Symmetric Tree) trong C++

Cho cây nhị phân, kiểm tra xem nó có đối xứng với chính nó hay không. Cây nhị phân đối xứng tạo ra ảnh phản chiếu của chính nó.

Ví dụ

Input 1:

Output: True

Giải thích: Cây tạo ảnh phản chiếu của chính nó.

Input 2:

Output: False

Giải thích: Không tạo ảnh phản chiếu.

Cách tiếp cận

Cây đối xứng = ảnh phản chiếu của chính nó → kiểm tra nút trái và nút phải có giống nhau không.

• Hàm Boolean helper(root1, root2) kiểm tra 2 gốc của cùng cây
• Nếu rỗng/NULL → True
• Đệ quy kiểm tra nút trái của root1 với nút phải của root2 và ngược lại
• Trả về False nếu không thỏa mãn

Code C++

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

struct treenode {
    int data;
    treenode *left;
    treenode *right;
};

struct treenode* createNode(int d) {
    struct treenode* root = new treenode;
    root->data = d;
    root->left = NULL;
    root->right = NULL;
    return root;
}

bool helper(struct treenode* root1, struct treenode* root2) {
    if (root1 == NULL && root2 == NULL) return true;
    if (root1 && root2 && root1->data == root2->data)
        return (helper(root1->left, root2->right) && helper(root1->right, root2->left));
    return false;
}

bool isSymmetry(struct treenode* root) {
    return helper(root, root);
}

int main() {
    struct treenode* root = NULL;
    root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(2);
    root->left->right = createNode(7);
    root->left->left = createNode(5);
    root->right->left = createNode(5);
    root->right->right = createNode(7);
    if (isSymmetry(root)) cout << "True" << endl;
    else cout << "False" << endl;
    return 0;
}

Kết quả

False

Cây không đối xứng → False.