C++로 두 이진 트리가 같은지 확인하는 방법 (Same Tree 문제 풀이)

두 개의 이진 트리가 주어졌을 때, 이 두 트리가 서로 같은지 판별하는 함수를 정의해야 합니다. 두 이진 트리는 구조적으로 완전히 동일하고 각 노드의 값까지 일치할 때 '같은 트리(Same Tree)'로 간주됩니다.

예를 들어 입력이 [1,2,3]과 [1,2,3]으로 동일하다면 출력은 True(참)가 됩니다.

문제 해결 접근 방법

이 문제는 재귀(Recursion)를 활용하면 간단하게 해결할 수 있습니다. 다음 단계를 따릅니다.

• 두 개의 트리 노드 p와 q를 매개변수로 받는 isSameTree 함수를 정의합니다.

• p와 q가 모두 NULL이라면 두 트리 모두 빈 트리이므로 true를 반환합니다.

• p 또는 q 중 하나만 NULL이라면 구조가 서로 다르므로 false를 반환합니다.

• p의 값(val)과 q의 값(val)이 같고, isSameTree(p->left, q->left)와 isSameTree(p->right, q->right)의 재귀 호출 결과가 모두 true라면 true를 반환합니다.

• 그 외의 경우에는 false를 반환합니다.

C++ 구현 예제

아래 전체 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
        int val;
        TreeNode *left, *right;
        TreeNode(int data){
            val = data;
            left = NULL;
            right = NULL;
        }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        }
        else{
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }
        else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode* q){
        if (p == NULL && q == NULL)
            return true;
        if (p == NULL || q == NULL)
            return false;
        if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right))
            return true;
        return false;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3}, v1 = {1,2,3};
    TreeNode *root1 = make_tree(v);
    TreeNode *root2 = make_tree(v1);
    cout << (ob.isSameTree(root1, root2));
}

입력

{1,2,3}, {1,2,3}

출력

1

출력이 1(C++에서 true를 의미)인 것을 확인할 수 있습니다. 두 트리의 구조와 노드 값이 완전히 동일하기 때문입니다.

시간 및 공간 복잡도

시간 복잡도: O(n) — n은 트리의 노드 개수이며, 각 노드를 한 번씩만 방문합니다.
공간 복잡도: 최악의 경우 O(n) — 재귀 호출 스택의 깊이가 트리의 높이와 같기 때문입니다.