เขียนโค้ดตรวจสอบว่าต้นไม้สองต้นเหมือนกัน (Identical Trees) ใน C++

โจทย์

ได้รับต้นไม้สองต้น ตรวจสอบว่าทั้งสองต้น identical (เหมือนกันทุกประการ) หรือไม่

นิยาม Identical Trees

ต้นไม้สองต้น identical ก็ต่อเมื่อ:

1. โครงสร้าง (structure) เหมือนกันทุกอย่าง
2. ค่า (data) ของโหนดที่ตรงกันทุกคู่ มีค่าเท่ากัน

ตัวอย่าง

ทั้งสองต้นมีค่าและตำแหน่งโหนดเหมือนกัน → Identical

อัลกอริทึม (Recursive)

isIdentical(tree1, tree2):
    if both null: return true
    if one null, other not: return false
    if data different: return false
    return isIdentical(left1, left2) AND isIdentical(right1, right2)

โค้ดตัวอย่าง

#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 = nullptr;
    node->right = nullptr;
    return node;
}

bool isIdenticalTrees(Node* tree1, Node* tree2) {
    // ทั้งคู่ null
    if (tree1 == nullptr && tree2 == nullptr) return true;
    
    // หนึ่ง null หนึ่งไม่ null
    if (tree1 == nullptr || tree2 == nullptr) return false;
    
    // เปรียบเทียบค่า และ recursive ตรวจสอบลูก
    return (tree1->data == tree2->data) &&
           isIdenticalTrees(tree1->left, tree2->left) &&
           isIdenticalTrees(tree1->right, tree2->right);
}

int main() {
    // Tree 1
    Node* root1 = 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);
    
    // Tree 2 (เหมือน Tree 1)
    Node* root2 = insertNode(4);
    root2->left = insertNode(5);
    root2->right = insertNode(0);
    root2->left->left = insertNode(1);
    root2->left->right = insertNode(9);
    root2->right->left = insertNode(7);
    
    cout << "Both the given trees are ";
    if (isIdenticalTrees(root1, root2)) cout << "identical";
    else cout << "not identical";
    
    return 0;
}

ผลลัพธ์

Both the given trees are identical

Iterative Version (BFS)

bool isIdenticalIterative(Node* root1, Node* root2) {
    if (!root1 && !root2) return true;
    if (!root1 || !root2) return false;
    
    queue<pair<Node*, Node*>> q;
    q.push({root1, root2});
    
    while (!q.empty()) {
        auto [n1, n2] = q.front(); q.pop();
        
        if (n1->data != n2->data) return false;
        
        if ((n1->left == nullptr) != (n2->left == nullptr)) return false;
        if ((n1->right == nullptr) != (n2->right == nullptr)) return false;
        
        if (n1->left) q.push({n1->left, n2->left});
        if (n1->right) q.push({n1->right, n2->right});
    }
    return true;
}

Complexity

• Time: O(N) - N = จำนวนโหนด (ต้องเช็คทุกโหนด)
• Space (Recursive): O(H) - H = ความสูงต้นไม้
• Space (Iterative): O(W) - W = ความกว้างสูงสุด

สรุป

การตรวจสอบ identical trees เป็นปัญหาพื้นฐานของ tree traversal Recursive version เขียนง่ายที่สุด Iterative version ใช้เมื่อ tree ลึกมาก ควรระวัง stack overflow ใน recursive version สำหรับ skewed trees