※ 引述 《smart0eddie (smart0eddie)》 之铭言：
:
: 2024-07-15
: 2196. Create Binary Tree From Descriptions
:
: 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.
翻译:
给你一串叙述关系的阵列
告诉你他的父节点
子节点 还有子节点在左边还是右边
叫你照着关系做一个树
思路:
先纪录全部的关系到全域的unordered map 里面
这样比较好用那些资讯
然后要做一棵树的话就要先找到他的起点
起点是父节点
但绝对不会是子节点
所以再用一个阵列纪录所有子节点
然后找没出现在子节点的父节点
就可以找到起点了
然后用起点的值去map里面找 一直找
就好了
```cpp
/**
* 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), ri
ght(right) {}
* };
*/
class Solution {
public:
unordered_map<int,pair<int,int>> save;
void go(TreeNode* n)
{
if(save[n->val].first!=0)
{
n->left = new TreeNode(save[n->val].first);
go(n->left);
}
if(save[n->val].second!=0)
{
n->right = new TreeNode(save[n->val].second);
go(n->right);
}
return ;
}
TreeNode* createBinaryTree(vector<vector<int>>& descriptions)
{
save.clear();
int len = descriptions.size();
TreeNode* res = new TreeNode();
unordered_set<int> save2;
for(int i = 0 ; i < len ; i ++)
{
(descriptions[i][2]==0)? save[descriptions[i][0]].second=description
s[i][1]:save[descriptions[i][0]].first=descriptions[i][1];
save2.insert(descriptions[i][1]);
}
for(int i = 0 ; i < len ; i ++)
{
if(save2.find(descriptions[i][0]) == save2.end())
{
res->val = descriptions[i][0];
go(res);
break;
}
}
return res;
}
};
```