M'S Blog

M'S Blog

WWDC20 student challenge Winner!

leetcode 987 - Vertical Order Traversal of a Binary Tree

최대 1 분 소요

문제

leetcode 987 - Vertical Order Traversal of a Binary Tree 풀러가기

문제 분석

tree를 bfs나 dfs로 탐색하면서

왼쪽 자식의 경우에는 현재 노드의 column-1, row-1을 해주고

오른쪽 자식의 경우에는 현재 노드의 column+1, row-1을 해준다.

문제 코드(C++)

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    class Solution {
    public:
        vector<vector<int>> verticalTraversal(TreeNode* root) {
            map<int, pair<int, int>> m;
            
            vector<vector<int>> ans;
            
            queue<TreeNode*> q;
            
            q.push(root);
            m[root->val] = make_pair(0,0);
            while(!q.empty()){
                TreeNode* curr = q.front();
                q.pop();
                if(curr->left){
                    q.push(curr->left);
                    m[curr->left->val] = make_pair(m[curr->val].first-1, m[curr->val].second-1);
                }
                if(curr->right){
                    q.push(curr->right);
                    m[curr->right->val] = make_pair(m[curr->val].first+1, m[curr->val].second-1);
                }
            }
            vector<pair<int, pair<int,int>>> tmp(m.begin(), m.end());
            
            sort(tmp.begin(), tmp.end(), [](pair<int, pair<int,int>> x, pair<int, pair<int,int>> y){
                if(x.second.first != y.second.first){
                    return x.second.first < y.second.first;
                }else if(x.second.second != y.second.second){
                    return x.second.second>y.second.second;
                }else{
                    return x.first<y.first;
                }
            });
            
            for(int i=0;i<tmp.size();i++){
                int curr = tmp[i].second.first;
                vector<int> t;
                t.push_back(tmp[i].first);
                for(int j=i+1; j<tmp.size();j++){
                    if(tmp[j].second.first==curr){
                        t.push_back(tmp[j].first);
                        i=j;
                    }else{
                        break;
                    }
                }
                ans.push_back(t);
            }
            
            return ans;
        }
    };
    		cs
    • 12~23번째 줄 : tree를 bfs로 탐색하면서 row, column 값으로 구성된 map을 채운다. map을 사용한 이유는 key가 없는 경우에 자동으로 그 key를 생성하기 때문이다.
    • 24~34번째 줄 : sort를 하기 위해 각 노드의 위치 정보가 담긴 map을 vector로 옮긴다.
      • 옮긴 후에는 sorting을 하는데, 이때 1) column이 작은 순 2) column이 같다면 row가 큰 순 3) column,row가 같다면 노드의 값이 작은 순 으로 정렬을 해야 한다.
    • 36~49번째 줄 : 정렬 된 결과를 이용하여, column이 같은 값끼리 같은 vector에 넣고 그 vector를 전체 정답 vector에 넣어준다.

    Runtime: 4 ms, faster than 90.10% of C++ online submissions for Vertical Order Traversal of a Binary Tree.

    Memory Usage: 12.3 MB, less than 84.03% of C++ online submissions for Vertical Order Traversal of a Binary Tree.






아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고