23.03.15. 풀었던 문제들

Leetcode 958. Check Completeness of a Binary Tree

첫 접근

 첫 접근은 각 layer를 검사하는 방식으로 생각을 했는데 생각보다 귀찮은 경우의 수가 많아서 binary tree를 array로 표기하려 했다. 이렇게 표기해도 된다고 생각했던 이유는 vertex size가 최대 100이었기 때문이었다. 그러나 1자로 길게 늘어진 tree의 경우에는 최대 $2^{100}$의 array가 필요했고 이건 아니다 싶어 다른 방법으로 전환했다.

 

 

두 번째 접근 : time, space O(n)

 각 layer마다 탐색하는 방식이다. 각 layer에서 아래와 같은 조건으로 탐색할 수 있다.

• 각 layer 탐색 시
  • left -> right 순서대로 탐색할 때 null이 나온 후 notnull이 나온다면 false이다.
  • 이전 layer가 incomplete이든 complete든 상관없이 현 layer가 모두 null이면 true이다. - 1번 조건
  • 이전 layer가 incomplete일 때 이전 layer size의 2배보다 작다면 false - 2번 조건
  • 이전 layer가 complete일 때 이전 layer size의 2배보다 작다면 incomplete, 2배라면 complete이다. - 3번 조건

// Runtime 0 ms Beatse 100%
// Memory 10.6 MB Beats 29.89%

class Solution {
public:
    vector<TreeNode*> arr;
    // isPreviousComplete : 이전 단계가 incomplete
    bool fillarr(bool isPreviousIncomplete){
        // null 이후에 notnull이 오는지 + 현 layer 탐색
        vector<TreeNode*> curarr;
        bool hasNull = false;
        for(TreeNode* t : arr){
            if(t->left){
                if(hasNull) return false;
                curarr.push_back(t->left);
            }
            else hasNull = true;
            if(t->right){
                if(hasNull) return false;
                curarr.push_back(t->right);      
            }
            else hasNull = true;
        }

        if(curarr.size() == 0) return true; // 1번 조건
        if(isPreviousIncomplete && curarr.size() >= 1) return false; // 2번 조건
        if(curarr.size() != arr.size() * 2) isPreviousIncomplete = true; // 3번 조건
        arr = curarr;
        return fillarr(isPreviousIncomplete);
    }
    bool isCompleteTree(TreeNode* root) {
        arr.push_back(root);
        return fillarr(false);
    }
};

 

 

두번째 접근

 vector로 구현했는데 굳이 array를 사용할 필요가 없을 것 같아, queue로 바꾸었다. queue로 바꾸고 나니 BFS같은 느낌이 확 든다. 굳이 recurse할 필요 없이 풀 수도 있을 것 같아 그렇게도 풀었다. 그렇게 하면 recurse에 사용하는 memory가 절약되기도 한다.

// Runtime 0 ms Beatse 100%
// Memory 10.6 MB Beats 29.89%

class Solution {
public:
    queue<TreeNode*> q;
    // isPreviousComplete : 이전 단계가 incomplete
    bool fillarr(bool isPreviousIncomplete){
        // null 이후에 notnull이 오는지 + 현 layer 탐색
        bool hasNull = false;
        int prevsize = q.size();
        int k = prevsize;
        while(k--){
            TreeNode* t = q.front(); q.pop();
            if(t->left){
                if(hasNull) return false;
                q.push(t->left);
            }
            else hasNull = true;
            if(t->right){
                if(hasNull) return false;
                q.push(t->right);      
            }
            else hasNull = true;
        }
        
        int cursize = q.size();
        if(q.size() == 0) return true;
        if(isPreviousIncomplete && q.size() >= 1) return false;
        if(cursize != (prevsize * 2)) isPreviousIncomplete = true;
        return fillarr(isPreviousIncomplete);
    }
    bool isCompleteTree(TreeNode* root) {
        q.push(root);
        return fillarr(false);
    }
};

 

 

신박한 Solution

 다른 사람들의 solution을 읽던 중 굉장히 괜찮다고 느껴지는 게 있어 가져왔다. 각 layer를 검색하는 특징은 똑같은데 문제 조건을 아주 쉽게 구현했다.

• 현 layer를 queue에 넣는다.
• 만약 null인 값이 있다면 "탐색 시 null이 존재했다"라고 표기한다.
• 이후 계속 탐색하다 또 null인 값이 있다면 return false
• 탐색이 종료되면 return true

 

 queue에 들어가는 순서는 layer 0의 왼쪽->오른쪽, layer 1의 왼쪽->오른쪽, ... layer h의 왼쪽 -> 오른쪽 순서이다. 따라서 [null인 vertex] 이후에 [null이 아닌 vertex]가 들어온다면 무조건 문제 조건에 부합하지 않는 경우이다. 아주 직관적이면서도 간단하다.

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        bool nullBeforeNode = false;
        queue<TreeNode*> q;
        q.push(root);
        
        while(size(q))
        {
            auto node = q.front();
            q.pop();
            
            if(node == NULL) nullBeforeNode = true;
            else 
            {
                if(nullBeforeNode == true) return false;
                q.push(node->left);
                q.push(node->right);
            }
        }
        
        return true;
    }
}

 

시간복잡도

 결국 모든 vertex를 봐 주어야 하므로 O(n)이다.

 

공간복잡도

 recurse에 O(h), 그리고 vector나 queue에 모든 vertex가 들어가게 되므로 O(n)이다.