문제 요약:
Input:
descriptions = [[20,15,1], [20,17,0], [50,20,1], [50,80,0], [80,19,1]]
Output:
[50,20,80,15,17,19]
descriptions의 각 요소가 의미하는 다음과 같다
[0]: 부모노드의 값
[1]: 자식노드의 값
[2]: 부모로부터의 자식노드의 위치
주어진 descriptions의 내용을 토대로 Binary Tree 를 만들어 반환하라
문제 분석:
- 주어지는 descriptions는 Binary Tree 가 유효하도록 case가 주어진다
- descriptions에는 순서와 상관없이 들어온다
- 각 값들은 unique 하게 들어온다 (중복 X)
풀이 과정:
처음으로 감이 잘 오지 않는 문제였다
descriptions의 정보들을 나눠서 나눈 정보들을 토대로 보다 쉽게 Binary Tree를 만들거나
descriptions를 인덱스에 따라 Binary Tree를 탐색하면서 계속 Tree를 늘려나가는 방식으로 만들려고 했으나, 위의 문제 분석 내용 중에 descriptions의 순서가 제대로 들어오지 않아 Tree가 만들어지는 도중 끊긴 트리가 만들어지는 경우가 있으므로 TreeNode * 자료형의 벡터 인스턴스를 만들어서 끊긴 Tree들에 대한 목록을 만드는 방법을 생각을 했다
첫 번째 정보를 나누는 방식은 정보를 어떻게 나눠야 하는지 전혀 감이 오지 않는다는 것이 문제였고, 두 번째는 끊긴 Tree끼리 서로 연결할 확실한 증거를 확보할 방법이 떠오르지가 않았다.
저번 문제에서의 교훈(?)을 통해 빠르게 포기했다
풀이 결과:
없음
배운 점 및 코드:
STL에 대해 잘 모르는 것도 있는데 Tree형식에 좀 약하다는 것을 다시금 깨달았다(공부하자)
for (auto& element : container) {}에 대해 배우게 되었다
이것을 사용하지 않으면 for (container <data type>::iterator element = container.begin(); element!= container.end(); ++element) {}라는 끝도 없는 긴 방식을 사용해야 하는데, for (auto& element : container) {}를 사용하는 편이 가독성에도 좋고 사용하기에도 편한 것 같다
위 방식은 여기에 잘 나와있다
아래는 답지 내용을 분석한 코드인데 위의 문제 풀이에서 처음에 나왔던 descriptions의 정보를 나누는 방식을 Graph로 하고 만들어진 Graph를 통해 BFS방식으로 이진트리를 만드는 방식이다
/**
* 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) {}
* };
*/
#include <vector>
using namespace std;
class Solution {
public:
TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
// 부모와 자식 중복제거
// set은 중복을 허용하지 않는다
// 자바에서는 HashSet을 사용하고 C++에서는 unordered_set을 사용
// HashSet은 중복되지 않는 데이터를 효율적으로 관리하고 검색하는데 매우 유용함
unordered_set<int> children, parents;
// 부모와 자식 관계를 저장
// key, value값으로 key = 부모노드 value = left, right 자식노드를 묶는다
unordered_map<int, vector<pair<int, int>>> parentToChildren;
int parent, child, isLeft;
TreeNode *root, *parentNode, *childNode;
queue<TreeNode *> queue;
// 부모자식간에 관계를 그래프로 그리고, 만들어진 노드를 unordered_map에 넣음
for (auto& d : descriptions) {
parent = d[0];
child = d[1];
isLeft = d[2];
parents.insert(parent);
parents.insert(child);
children.insert(child);
// emplace_back 요소를 컨테이너에 추가
// insert와 다르게 요소를 만들어 전달하지 않고 컨테이너에 인자를 전달하여
// 컨테이너 내부에서 만들기 때문에 추가적인 복사나 이동이 발생하지 않음
parentToChildren[parent].emplace_back(child, isLeft);
}
// 여기서 자식에는 없지만 부모에는 있는 root노드를 찾음
for (auto it = parents.begin(); it != parents.end();) {
// 부모노드 목록에 있는 노드가 자식노드에 존재하면 삭제
if (children.find(*it) != children.end())
it = parents.erase(it);
else
++it;
}
// 최종적으로 하나 남은 부모노드가 root노드임
root = new TreeNode(*parents.begin());
//root노드부터 BFS를 통한 이진트리 생성
queue.push(root);
while (!queue.empty()) {
parentNode = queue.front();
queue.pop();
// 현재 부모 노드의 자식들을 순회
for (auto& childInfo : parentToChildren[parentNode->val]) {
child = childInfo.first;
isLeft = childInfo.second;
childNode = new TreeNode(child);
queue.push(childNode);
// 자식노드를 부모노드와 isLeft를 기준으로 부모노드에 붙임
if (isLeft)
parentNode->left = childNode;
else
parentNode->right = childNode;
}
}
return root;
}
};