전체 이진 트리(Full Binary Tree)는 모든 노드가 정확히 0개 또는 2개의 자식을 가지는 이진 트리를 의미합니다. 이 문제에서는 N개의 노드로 만들 수 있는 모든 전체 이진 트리의 목록을 구해야 합니다. 각 트리의 모든 노드는 node.val = 0의 값을 가져야 하며, 반환되는 트리들의 순서는 임의로 지정할 수 있습니다.
예를 들어 입력이 7이라면 다음과 같은 트리들이 생성됩니다.
해결 접근 방법
이 문제는 재귀 호출과 메모이제이션(Memoization)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 루트 노드 하나를 제외한 나머지 N-1개의 노드를 왼쪽 서브트리와 오른쪽 서브트리로 나누고, 각각에 대해 가능한 모든 전체 이진 트리를 재귀적으로 생성한 뒤 조합하는 것입니다.
정수 타입 키와 트리 벡터 타입 값을 저장하는 맵(map) m을 정의합니다.
N을 입력으로 받는 allPossibleFBT() 메서드를 정의합니다.
N이 1이면 값이 0인 단일 노드로 구성된 트리를 생성하여 반환합니다.
맵 m에 이미 키 N이 존재하면 m[N]을 그대로 반환하여 중복 계산을 방지합니다.
결과를 담을 배열 temp를 정의하고, req := N - 1로 설정합니다.
left를 1부터 req - 1까지 반복합니다.
right := req - left로 설정합니다.
left 또는 right가 2라면 전체 이진 트리를 만들 수 없으므로 다음 반복으로 넘어갑니다.
leftPart := allPossibleFBT(left), rightPart := allPossibleFBT(right)로 재귀 호출합니다.
j를 0부터 leftPart 크기 - 1까지 반복합니다.
k를 0부터 rightPart 크기 - 1까지 반복합니다.
값이 0인 새 노드 root를 생성합니다.
root의 왼쪽 자식 := leftPart[j], 오른쪽 자식 := rightPart[k]로 연결합니다.
root를 ans에 삽입합니다.
m[N] := ans로 설정한 후 ans를 반환합니다.
예제 코드(C++)
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
} else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr == NULL || curr->val == 0){
cout << "null" << ", ";
} else {
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
map < int, vector <TreeNode*> > m;
vector<TreeNode*> allPossibleFBT(int N) {
if(N == 1){
vector <TreeNode*> temp;
TreeNode *n = new TreeNode(1);
n->left = new TreeNode(0);
n->right = new TreeNode(0);
temp.push_back(n);
return temp;
}
if(m.count(N))return m[N];
vector <TreeNode*> ans;
int required = N - 1;
for(int left = 1; left < required; left++){
int right = required - left;
if(left == 2 || right == 2)continue;
vector <TreeNode*> leftPart = allPossibleFBT(left);
vector <TreeNode*> rightPart = allPossibleFBT(right);
for(int j = 0; j < leftPart.size(); j++){
for(int k = 0; k < rightPart.size(); k++){
TreeNode* root = new TreeNode(1);
root->left = leftPart[j];
root->right = rightPart[k];
ans.push_back(root);
}
}
}
return m[N] = ans;
}
};
main(){
vector<TreeNode*> v;
Solution ob;
v = (ob.allPossibleFBT(7)) ;
for(TreeNode *t : v){
tree_level_trav(t);
}
}입력
7
출력
[1, 1, 1, null, null, 1, 1, null, null, 1, 1, null, null, null, null] [1, 1, 1, null, null, 1, 1, 1, 1, null, null, null, null, null, null] [1, 1, 1, 1, 1, 1, 1, null, null, null, null, null, null, null, null] [1, 1, 1, 1, 1, null, null, null, null, 1, 1, null, null, null, null] [1, 1, 1, 1, 1, null, null, 1, 1, null, null, null, null, null, null]