표현 가능한 이진트리 (Kakao)

문제

수의 배열이 주어진다
각 수마다 그 수를 이진수로 표현하여 트리로 만들 수 있는지 판단하여
가능하다면 1, 불가능하다면 0을 저장한다

이진 트리를 수로 표현하는 방법

1. 이진트리에 더미노드를 추가하여 포화 이진트리로 만듦
   
   이진트리
   
   더미 노드를 추가한 이진트리

2. 위의 더미노드를 추가한 이진트리를 수로 변환
   -> 중위 순회를 하면서 왼쪽부터 더미노드면 0, 그냥 노드면 1
   위의 그림과 같은 경우 0111010으로 변환이 된다!

ex) 111은 이진트리로 표현할 수 있을까?
111 = (1101111)2
따라서 아래와 같은 이진트리로 생성이 가능하다

5와 같은 경우에는
이진수로 나타내면 101,
이는 이진트리로 생성이 불가능하다.. (루트가 더미노드가 되기 때문)

풀이

트리를 자료구조로 만들지 않고 배열 그대로 트리를 저장하는 방식을 사용

포화 이진트리를 만들려면 이진수를 2^n -1 자리수로 만들어야 한다!
(1레벨 트리는 2^1-1 = 1, 2레벨 트리는 2^2-1 = 3 ...)
빈 공간은 0으로 채움,,,
만약 63을 포화 이진트리로 만드려면
63 = (111111)2 이고,
이를 포화 이진트리로 만드려면

맨 왼쪽에 0을 채워서 (0111111)2로 변환, 더미노드를 사용해서 포화 이진트리를 만드는 것이 가능하다

배열의 앞에 0을 추가하는 방식보다는
배열을 0으로 초기화하고 뒤에 0을 넣는 방식이 더 편하므로 배열을 뒤집어서 사용한다...

1. 주어진 수를 이진수로 표현, 배열에 저장

		while(1){
            if(tmp == 0 || tmp == 1){
                arr[pnt] = tmp ;
                pnt++;
                break;
            }else{
                arr[pnt] = tmp%2;
                pnt++;
                tmp = tmp/2;
            }
        }

원래 이진수를 만들 때는 계속해서 2로 나눈 나머지를 구한 후 수를 반대로 가져와야 한다

위에서 설명한 이유로 이진수를 반대로 사용해야 하므로 그냥 나눈 나머지를 순서대로 배열에 저장해준다
(남은 뒷공간에 0을 넣기 편해짐)

2. 이진 트리의 레벨 구함
   이진수가 1011 이라면 포화 이진트리로 표현하면 3레벨 트리로 나타낼 수 있다!
   (2레벨은 최대 3개수가 들어가므로)
   우선 레벨을 구해줘야 탐색이 가능하다

while(1){
            if(pnt>=pos*2){
                pos = pos*2;
            }else{
                break;
            }
        }

배열 길이보다 더 긴 2의 제곱수를 구해준다

3. 배열에 저장된 이진수를 탐색하면서 불가능 여부 판단

이진 트리로 만드는 것이 불가능하다는 것은
-> 어떠한 노드든 부모가 0인데 양쪽 자식중 하나라도 1인 경우!

더미노드는 트리의 끝에 붙이는 것인데 더미 밑에 진짜 노드가 나오면 잘못된 트리이다

void find(int x,int floor){
    int margin = floor/2;
    if(margin!=0){
       
        if(arr[x-1]==0){
            if(arr[x+margin-1]==1 ||arr[x-margin-1]==1 ){
                check=0;
                return;
            }
        }
        //printf("%d %d %d\n",x, arr[x+margin-1],arr[x-margin-1]);
        find(x-margin,margin);
        find(x+margin,margin);
        
    }
    
    
}

find 함수를 재귀적 탐색을 통해 볼가능한 것인지 확인함
x는 탐색할 위치, floor은 퍼지는 레벨!

만약 자신이 0이면서 양쪽 자식 노드중 하나라도 1이 있다면 불가능하다 체킹함!

11은 이진트리로 표현이 가능할까를 과정으로 나타냈다
우선 2로 나누면서 이진수로 나타내고 배열에 저장,
이 배열을 그대로 루트의 위치가 4임을 파악한 후,
4에서부터 재귀적으로 양방향 탐색을 한다
0 밑에 1인 자식이 나오는 경우는 없으므로 11은 이진트리로 가능한 수이다

코드

//  1 2 4 8 ... ()
#include <string.h>
#include <vector>
#include <stdio.h>
using namespace std;
char arr[20000];
int pnt = 0;
int pos;
int check=1;
// void divide(int x){
// 	if(x == 1 || x == 0){
// 		arr[pnt]= x+'0';
// 		pnt++;
// 	}else{
// 		divide(x/2);
// 		arr[pnt] = x%2+'0';
// 		pnt++;
// 	}
// }
// void make_num(int x){
// 	divide(x);
// }

void find(int x,int floor){
    int margin = floor/2;
    if(margin!=0){
       
        if(arr[x-1]==0){
            if(arr[x+margin-1]==1 ||arr[x-margin-1]==1 ){
                check=0;
                return;
            }
        }
        //printf("%d %d %d\n",x, arr[x+margin-1],arr[x-margin-1]);
        find(x-margin,margin);
        find(x+margin,margin);
        
    }
    
    
}
vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for(int num=0;num<numbers.size();num++){
        pnt = 0;
        long long tmp = numbers[num];
        memset(arr, 0 ,sizeof(char)*20000);
        while(1){
            if(tmp == 0 || tmp == 1){
                arr[pnt] = tmp ;
                pnt++;
                break;
            }else{
                arr[pnt] = tmp%2;
                pnt++;
                tmp = tmp/2;
            }
        }
	    // for(int i=0;i<pnt;i++){
	    // printf("%c",arr[i]);
	    // }
	    // printf("\n");
        
        pos = 1;
        while(1){
            if(pnt>=pos*2){
                pos = pos*2;
            }else{
                break;
            }
        }
        check=1;
        //printf("%d %d\n",pos,pnt);
        find(pos,pos);
        answer.push_back(check);
    }
        
    return answer;
}