C++로 두 이진 트리에서 일치하지 않는 첫 번째 리프 노드 찾기

문제 개요

두 개의 이진 트리가 주어졌을 때, 두 트리를 비교하여 서로 일치하지 않는 첫 번째 리프(leaf) 노드를 찾아야 합니다. 만약 모든 리프 노드가 일치한다면 아무것도 출력하지 않습니다.

위 그림과 같은 두 트리가 주어지면, 일치하지 않는 첫 번째 리프 노드는 11과 15입니다.

접근 방법: 스택을 이용한 동시 전위 순회

이 문제는 스택을 활용한 반복적(iterative) 전위 순회(preorder traversal)를 통해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

각 트리마다 별도의 스택을 준비한 뒤, 루트 노드부터 시작해 자식 노드들을 스택에 계속 push하면서 스택의 최상단(top) 노드가 리프 노드가 될 때까지 탐색을 진행합니다. 두 스택 모두에서 리프 노드를 얻었다면, 두 최상단 노드의 데이터 값을 비교합니다. 값이 같다면 다음 리프 노드를 찾기 위해 순회를 계속하고, 값이 다르다면 해당 두 노드가 바로 일치하지 않는 첫 번째 리프이므로 출력하고 종료합니다.

알고리즘 단계

1. 두 트리의 루트를 각각의 스택에 push합니다.
2. 각 스택에서 노드를 꺼내며, 리프 노드가 나올 때까지 오른쪽 자식과 왼쪽 자식을 순서대로 push합니다.
3. 두 스택에서 얻은 리프 노드의 값을 비교합니다.
4. 값이 다르면 결과를 출력하고 종료하고, 같으면 2번 단계부터 반복합니다.
5. 한쪽 스택이라도 비게 되면 더 이상 비교할 리프가 없으므로 종료합니다.

C++ 구현 예제

#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<Node*> 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 != NULL && top2 != NULL ){
            if (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);
}

실행 결과

First non matching leaves are: 11 15

정리

이 방식은 재귀 호출 없이 스택만으로 두 트리를 동시에 순회하기 때문에, 깊이가 깊은 트리에서도 스택 오버플로우 위험 없이 안정적으로 동작합니다. 시간 복잡도는 두 트리의 노드 수에 비례하는 O(n)이며, 공간 복잡도 역시 스택 크기에 의해 O(h)(h는 트리의 높이) 수준입니다. 두 트리의 리프 노드 순서를 왼쪽에서 오른쪽으로 차례대로 비교해야 하는 유사한 문제에도 응용할 수 있는 유용한 패턴입니다.