C++로 해결하는 반전된 하위 트리(Inverted Subtree) 문제

문제 개요

이진 트리 두 개가 주어졌다고 가정해 보겠습니다. 하나는 source(원본), 다른 하나는 target(대상)입니다. 우리가 확인해야 할 것은 source의 어떤 반전(inversion) 형태 T가 target의 하위 트리(subtree)로 존재하는지 여부입니다.

여기서 '하위 트리로 존재한다'는 것은 target 내부에 어떤 노드가 있고, 그 노드를 루트로 하는 부분 구조가 자손 노드까지 포함하여 T와 값·구조 측면에서 완전히 동일하다는 의미입니다.

반전(inversion)의 정의

어떤 트리가 다른 트리의 반전이라고 말할 수 있는 조건은 다음 중 하나를 만족하는 경우입니다.

• 두 트리가 모두 비어 있는 경우
• 왼쪽과 오른쪽 자식이 선택적으로 서로 바뀌어(swap) 있고, 그 왼쪽 및 오른쪽 하위 트리들 역시 각각 서로의 반전인 경우

예시

예를 들어 입력이 아래와 같은 source 트리라고 가정해 봅시다.

그리고 target 트리는 다음과 같습니다.

이 경우 출력 결과는 True가 됩니다. source 트리의 좌우 자식 일부를 적절히 뒤집으면 target 안에서 동일한 구조를 찾을 수 있기 때문입니다.

풀이 접근 방법

이 문제는 재귀(recursion)를 활용하면 깔끔하게 해결할 수 있습니다. 크게 두 개의 함수로 구성됩니다.

1. check() 함수 — 두 노드의 동일성 검사

• check(node1, node2) 함수를 정의합니다.
• node1과 node2가 모두 null이면 true를 반환합니다. (두 트리 모두 비어 있다면 반전 관계에 해당)
• node1 또는 node2 중 하나만 null이면 false를 반환합니다. (구조가 맞지 않음)
• node1의 값(val)과 node2의 값이 같지 않으면 false를 반환합니다.
• op1 := check(node1의 왼쪽, node2의 왼쪽) AND check(node1의 오른쪽, node2의 오른쪽) — 순서가 그대로인 경우
• op2 := check(node1의 오른쪽, node2의 왼쪽) AND check(node1의 왼쪽, node2의 오른쪽) — 좌우가 바뀐 경우
• op1 또는 op2 중 하나라도 true라면 true를 반환합니다.

2. solve() 함수 — target 전체 탐색

• solve(source, target) 함수를 정의합니다.
• source와 target이 모두 비어 있으면 true를 반환합니다.
• source 또는 target 중 하나만 null이면 false를 반환합니다.
• op1 := check(target, source)를 호출하여 현재 위치에서 반전 여부를 검사합니다.
• op1이 true이면 즉시 true를 반환합니다.
• 그렇지 않다면 target의 왼쪽 하위 트리와 오른쪽 하위 트리를 재귀적으로 탐색하여, 그중 하나라도 성공하면 true를 반환합니다.

즉, 이 알고리즘은 target 트리의 모든 노드를 후보 루트로 삼아, 각 위치에서 source(및 그 좌우 반전 형태)와 일치하는지를 재귀적으로 검사하는 방식으로 동작합니다.

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;
    }
};
class Solution {
    public:
    bool check(TreeNode* node1, TreeNode* node2){
        if(!node1 && !node2)
        return true;
        if(!node1 || !node2)
        return false;
        if(node1->val != node2->val) {
            return false;
        }
        bool op1 = check(node1->left, node2->left) && check(node1->right, node2->right);
        bool op2 = check(node1->right, node2->left) && check(node1->left, node2->right);
        return op1 || op2;
    }
    bool solve(TreeNode* source, TreeNode* target) {
        if(!target && !source)
            return true;
        if(!target || !source)
            return false;
        bool op1 = check(target, source);
        if(op1)
            return true;
        return solve(source, target->left) || solve(source, target->right);
    }
};
main(){
    Solution ob;
    TreeNode *target = new TreeNode(6);
    target->left = new TreeNode(3);
    target->right = new TreeNode(1);
    target->right->left = new TreeNode(3);
    target->right->right = new TreeNode(2);
    target->right->right->left = new TreeNode(4);
    TreeNode *source = new TreeNode(1);
    source->left = new TreeNode(2);
    source->right = new TreeNode(3);
    source->left->right = new TreeNode(4);
    cout << (ob.solve(source, target));
}

입력

TreeNode *target = new TreeNode(6);
target->left = new TreeNode(3);
target->right = new TreeNode(1);
target->right->left = new TreeNode(3);
target->right->right = new TreeNode(2);
target->right->right->left = new TreeNode(4);
TreeNode *source = new TreeNode(1);
source->left = new TreeNode(2);
source->right = new TreeNode(3);
source->left->right = new TreeNode(4);

출력

1

출력값 1은 true를 의미합니다. 즉, source 트리의 반전 형태 중 하나가 target 트리의 하위 트리로 실제로 존재함을 확인할 수 있습니다.