표현 가능한 이진트리 [Lv. 3] (C++)

프로그래머스

트리가 있을 때 리프 노드에 더미 노드를 넣어 포화 이진트리로 만듭니다.

이 트리를 중위순회 한다고 할 때 더미 노드는 0, 기존 노드는 1을 넣습니다.

수를 입력받을 때 이 수가 위 처럼 표현이 가능한지 체크하면 됩니다.

더미 노드는 자식노드가 없기 때문에 자식 노드를 가진 0이 나온다면 불가능한게 됩니다.

 

풀이 방법

더미 노드는 자식 노드를 가질 수 없으며

모든 부모 노드는 2개의 자식 노드를 가지고 있습니다.

만일 부모 노드가 0이라면 표현 불가능한 노드입니다.

 

포화 이진트리로 만들기 위해 많은 0을 추가했기 때문에

부모 노드가 0인 경우가 있을 수 있습니다.

 

루트 노드부터 시작하여 왼쪽, 오른쪽 자식을 서브 트리로 분리합니다.

왼쪽 트리가 표현 가능 하면서 오른쪽 트리도 표현 가능하고

루트 노드가 0이 아니라면 해당 수는 이진트리로 표현이 가능합니다.

 

DFS 형식으로 재귀하여 반복하면 문제를 쉽게 해결할 수 있습니다.

 

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

string itob(long long num)
{
    string ret;
    while(num > 0)
    {
        if (num % 2 == 0)
            ret = "0" + ret;
        else
            ret = "1" + ret;
        
        num /= 2;
    }
    
    long long p = 0;
    while (p < ret.size())
        p = p * 2 + 1;
    
    while (p > ret.size())
        ret = "0" + ret;
    
    return ret;
}

bool isZero(string bit)
{
    for (auto& c : bit)
        if (c != '0')
            return false;
    return true;
}

bool DFS(string bit)
{
    if (bit.size() <= 1 || isZero(bit))
        return true;
    
    int mid = bit.size() / 2;
    string left = bit.substr(0, mid);
    string right = bit.substr(mid + 1);
    
    return DFS(left) && bit[mid] == '1' && DFS(right);
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    
    for (long long num : numbers)
    {
        if (DFS(itob(num)))
            answer.push_back(1);
        else
            answer.push_back(0);
    }

    return answer;
}