Viết code kiểm tra hai cây giống nhau C++

Trong bài toán này, cho hai cây. Nhiệm vụ viết code kiểm tra hai cây có giống hệt nhau (identical) hay không.

Hai cây identical nếu các phần tử có cùng giá trị và cùng vị trí (cấu trúc).

Ví dụ

Cả hai cây cùng giá trị và vị trí nên identical.

Để kiểm tra: duyệt đồng thời hai cây, so sánh từng nút. Nếu bất kỳ nút nào khác nhau trả về false. Nếu duyệt xong hoặc cả hai rỗng trả về true.

Ví dụ minh họa

#include <iostream>
using namespace std;

class node {
public:
    int data;
    node* left;
    node* right;
};

node* insertNode(int data) {
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return Node;
}

bool isIdentricalTrees(node* tree1, node* tree2) {
    if (tree1 == NULL && tree2 == NULL)
        return true;
    if (tree1 != NULL && tree2 != NULL) {
        return (tree1->data == tree2->data &&
                isIdentricalTrees(tree1->left, tree2->left) &&
                isIdentricalTrees(tree1->right, tree2->right));
    }
    return false;
}

int main() {
    node* root1 = insertNode(4);
    node* root2 = insertNode(4);
    
    root1->left = insertNode(5);
    root1->right = insertNode(0);
    root1->left->left = insertNode(1);
    root1->left->right = insertNode(9);
    root1->right->left = insertNode(7);
    
    root2->left = insertNode(5);
    root2->right = insertNode(0);
    root2->left->left = insertNode(1);
    root2->left->right = insertNode(9);
    root2->right->left = insertNode(7);
    
    cout << "Hai cây cho trước ";
    if (isIdentricalTrees(root1, root2))
        cout << "giống nhau";
    else
        cout << "khác nhau";
    
    return 0;
}

Kết quả

Hai cây cho trước giống nhau