[LeetCode] 2196. Create Binary Tree From Descriptions

https://leetcode.com/problems/create-binary-tree-from-descriptions/description/

leetcode - Create Binary Tree From Descriptions

문제 유형 : 이진트리

문제 난이도 : Medium

 

 

문제

You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,

• If isLefti == 1, then childi is the left child of parenti.
• If isLefti == 0, then childi is the right child of parenti.

Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid.

 

descriptions라는 2D 정수 배열을 얻는다. 

descriptions[i] = [parent_i, child_i, isLeft_i]는 child_i가 parent_i의 자식이란 뜻이고,
isLeft == 1이면 왼쪽자식, 0이면 오른쪽 자식이라는 뜻이다.

 

이진트리를 구성하여 root를 반환하시오.

트리는 항상 유효하도록 구성됩니다.

 

풀이

<int, TreeNode*>의 해시맵 mp를 만든다.

집합 자료구조도 만들어놓는다.

2D배열을 순회하면서, 해시맵에 노드를 저장시키고 노드들 간의 관계를 지어준다.

자식노드라고 명시된 적이 있으면, 집합에 자식노드의 key값을 넣는다.

 

집합에 없는 한 요소의 key를 찾고, root = mp[해당 key]를 하여 반환한다.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        unordered_map<int, TreeNode*> mp;
        unordered_set<int> children;
        
        for(const auto &description : descriptions) {
            int parentNum = description[0];
            int childNum = description[1];
            int isLeft = description[2];

            if(mp.find(childNum) == mp.end()) {
                mp[childNum] = new TreeNode(childNum);
            }

            if(mp.find(parentNum) == mp.end()) {
                mp[parentNum] = new TreeNode(parentNum);
            }

            if(isLeft) {
                mp[parentNum]->left = mp[childNum];
            } else {
                mp[parentNum]->right = mp[childNum];
            }

            children.insert(childNum);
        }

        TreeNode* root;;
        for(const auto &description : descriptions) {
            int parentNum = description[0];
            if(children.find(parentNum) == children.end()) {
                root = mp[parentNum];
                break;
            }
        }

        return root;
    }
};