23.04.20. 풀었던 문제들

Leetcode 662. Maximum Width of Binary Tree

첫 번째 접근 (Wrong)

 모든 vertex에 대해 해당 vertex가 몇 번째 vertex인지 index를 매긴다. (binary tree를 array로 변환하는 것과 같이) left가 있으면 cur vertex index * 2, right는 cur vertex index * 2 + 1로.

 그러나 이렇게 풀면 문제 제한조건에서 vertex가 max 3000개이므로 2^3000을 계산해야 한다. 엄...이다. overflow가 나지 않는 방법을 생각해야 한다.

typedef pair<int, int> pii;

class Solution {
public:
    vector<pii> depthInfos; // depthInfos[i].first : depth i의 min val, .second : max val.
    void dfs(TreeNode* cur, int depth, int order){
        depthInfos[depth].first = min(depthInfos[depth].first, order);
        depthInfos[depth].second = max(depthInfos[depth].second, order);
        if(cur->left){
            dfs(cur->left, depth+1, 2*order);
        }
        if(cur->right){
            dfs(cur->right, depth+1, 2*order + 1);
        }
    }
    int widthOfBinaryTree(TreeNode* root) {
        depthInfos.resize(3001);
        for(pii& depthInfo : depthInfos){
            depthInfo.first = 99999;
            depthInfo.second = -99999;
        }
        dfs(root, 0, 1);
        int answer = -1;
        for(pii depthInfo : depthInfos){
            answer = max(answer, depthInfo.second - depthInfo.first);
        }
        return answer+1;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

 

 

두 번째 접근

 BFS의 level별 탐색을 이용하고, 아래 표처럼 각 level 탐색 시 index를 0부터 초기화해서 센다면 어떨까? 각 level에서 max width가 INT_MAX를 넘지 않는다고 했으므로 worst case 2*INT_MAX가 각 index에 들어갈 수 있을 것이다.

level 0				0
level 1		0				1
level 2	0		1		2		3
...

 

• level 별 BFS를 한다.
  • 각 level 탐색 시, index를 0부터 시작한다. ... 1
  • left가 NOT NULL이면 index * 2를, right가 NOT NULL이면 index * 2 + 1을 저장한다.
    • 그러면 해당 level의 width는 q.back() - q.front()를 이용해 알 수 있다.
  • 이 때 index값이 INT_MAX인 경우 다음 level 탐색 시(2*index) overflow가 나므로 int 대신 long long을 이용한다. ... 2

// Runtime 12 ms Beats 45.41%
// Memory 17.4 MB Beats 25.97%

typedef long long ll;

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        queue<pair<TreeNode*, ll>> q; // .first : root, .second : index

        ll answer = -1;
        q.push({root, 0});
        while(!q.empty()){
            int curLevelSize = q.size();

            // *** 핵심 trick 2 : queue에는 항상 NOT NULL인 pointer가 들어가 있다. 따라서 q.back() index - q.front() index를 하면 width이다.
            // 단, 이 값이 INT_MAX일 때는 다음 level 탐색 시 overflow가 나므로 long long으로 풀어야 한다.
            answer = max(answer, q.back().second - q.front().second + 1); // answer : max sign integer
            int startIdx = q.front().second;
            while(curLevelSize--){ // BFS level별 탐색 trick
                TreeNode* topNode = q.front().first;
                int topIndex = q.front().second - startIdx; // *** 핵심 trick 1 : 시작 index를 0으로 초기화한다.
                q.pop();

                if(topNode->left){
                    q.push({topNode->left, 2L*topIndex});
                }
                if(topNode->right){
                    q.push({topNode->right, 2L*topIndex + 1});
                }
            }

        }

        return (int)answer;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

 

시간복잡도

 BFS 한 번이므로 O(V+E), E = 2V이므로 O(V)

 

공간복잡도

 q에 worst case O(V)만큼 들어간다. 따라서 O(V)

 

후기

 예전에 leetcode 풀기 시작했던 초창기에 BFS를 level별로 탐색해는 코드를 본 적 있었다. 그 코드는 굳이?였는데 이 문제는 BFS level별 탐색이 꼭 필요한 문제였다. 또 한가지 배워간다.