หา Leaf แรกที่ไม่ตรงกันของ Binary Tree สองต้นใน C++

ให้ Binary Tree สองต้น หา Leaf แรกที่ไม่ตรงกัน (ในลำดับ Preorder) หากไม่มี Leaf ที่ไม่ตรงกัน ให้ไม่แสดงอะไร

Leaf แรกที่ไม่ตรงกันคือ 11 และ 15

อัลกอริทึม

ใช้ Iterative Preorder Traversal พร้อมกันสำหรับทั้งสองต้น โดยใช้ Stack แยกกัน

1. Push root ของทั้งสองต้นลง Stack
2. Pop แล้วดันลงไปจนเจอ Leaf (Push right แล้ว left เพื่อให้ left ถูกประมวลผลก่อน)
3. เปรียบเทียบ Leaf ทั้งสอง หากต่างกัน แสดงผลและหยุด

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

#include <iostream>
#include <stack>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
};

Node* getNode(int x) {
    Node* newNode = new Node;
    newNode->data = x;
    newNode->left = newNode->right = NULL;
    return newNode;
}

bool isLeaf(Node* t) {
    return (t->left == NULL && t->right == NULL);
}

void findUnmatchedNodes(Node* t1, Node* t2) {
    if (t1 == NULL || t2 == NULL)
        return;

    stack s1, s2;
    s1.push(t1); s2.push(t2);

    while (!s1.empty() || !s2.empty()) {
        if (s1.empty() || s2.empty())
            return;

        Node* top1 = s1.top(); s1.pop();
        while (top1 && !isLeaf(top1)) {
            s1.push(top1->right);
            s1.push(top1->left);
            top1 = s1.top(); s1.pop();
        }

        Node* top2 = s2.top(); s2.pop();
        while (top2 && !isLeaf(top2)) {
            s2.push(top2->right);
            s2.push(top2->left);
            top2 = s2.top(); s2.pop();
        }

        if (top1 && top2 && top1->data != top2->data) {
            cout << "First non matching leaves are: " << top1->data << " " << top2->data << endl;
            return;
        }
    }
}

int main() {
    Node* t1 = getNode(5);
    t1->left = getNode(2);
    t1->right = getNode(7);
    t1->left->left = getNode(10);
    t1->left->right = getNode(11);

    Node* t2 = getNode(6);
    t2->left = getNode(10);
    t2->right = getNode(15);

    findUnmatchedNodes(t1, t2);
    return 0;
}

ผลลัพธ์

First non matching leaves are: 11 15