[HackerRank] Tree : Top View

https://www.hackerrank.com/challenges/tree-top-view/problem

Tree : Top View | HackerRank

문제 풀이)

 

   distance(level order) 와 vertical order를 기억하자.

 

   수직 별로 노드를 저장하는 것, 처음 겪어보았다. 기억해두자.

 

   queue를 이용해서 left, right 노드들의 거리를 통해 수직 별로 노드를 저장할 수 있다.

 

   HackerRank의 discussion의 첫 설명에서 영어센스가 부족하여 이해하지 못했음..

 

   답은 expected이다. in fact가 아니고..

 

< 소스 코드 >

void topView(Node * root) {
        // multimap<int, Node*> mulMap;
        // set<int> disKey;
        map<int, Node*> verticalMap;
        queue<pair<Node*, int>> q; // node, distance
        q.push({root, 0});
        while(!q.empty())
        {
            Node* curNode = q.front().first;
            int curDistance = q.front().second;
            q.pop();
            if(verticalMap.find(curDistance) == end(verticalMap))
                verticalMap.insert({curDistance, curNode});
            // disKey.insert(curDistance);

            if(curNode->left)
                q.push({curNode->left, curDistance - 1});
            if(curNode->right)
                q.push({curNode->right, curDistance + 1});
        }
        // for(auto& it : disKey)
        //    cout << mulMap.lower_bound(it)->second->data << ' ';
        for(auto& it : verticalMap)
            cout << it.second->data << ' ';
    }