표현 가능한 이진트리 150367

문제

접근 방법

이진 트리가 성립할 수 있는 조건을 생각해보면 된다.
자식이 존재한다면 부모가 존재해야 한다. 자식이 존재하지 않더라도 부모는 존재할 수 있다.
이것은 기본적인 내용이다.
더 깊이 생각해보면 자식의 자식이 존재하지만, 자식이 존재하지 않다면 그것은 잘못된 것이다. 즉 밑에 자식이 존재한다면 바로 위에는 부모가 존재해야 하고 이것이 사슬처럼 반복되어 루트까지 도달해야 한다는 것이다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
string tree;
char part(int left, int right)
{
    if (left == right)
    {
        return tree[left];
    }
    int mid = (left + right) >> 1;
    char lc = part(left, mid - 1);
    char rc = part(mid + 1, right);
    if (lc == 'f' || rc == 'f')
        return 'f';
    if (lc == '1' || rc == '1')
    {
        if (tree[mid] == '0')
            return 'f';
        return '1';
    }
    return tree[mid];
}
vector<int> solution(vector<ll> numbers)
{
    vector<int> answer;
    for (ll number : numbers)
    {
        tree.clear();
        while (number)
        {
            if (number % 2)
                tree.push_back('1');
            else
                tree.push_back('0');
            number >>= 1;
        }
        ll i = 1;
        while (tree.size() > (1 << i) - 1)
        {
            ++i;
        }
        while (tree.size() < (1 << i) - 1)
        {
            tree.push_back('0');
        }
        char ret = part(0, tree.size() - 1);
        if (ret == '1')
            answer.push_back(1);
        else
            answer.push_back(0);
    }
    return answer;
}

풀이

포화이진 트리의 경우 내 자식의 위치는 내 옆과 범위 끝의 절반이다. 이것을 활용하여 가장 밑에 자식까지 확인해주고 중간에 불가능해지면 'f'와 같이 표시하여 불가능을 알려준다.
자식 중 하나가 불가능하면 전체가 불가능하니 불가능을 반환한다.
자식 중 하나라도 1인데 본인이 0이면 불가능하므로 불가능을 반환한다.
자식이 둘 다 0이면 자신이 기준이므로 자신의 값을 반환하면 된다.