推 JIWP: 我好崇拜你 07/15 14:04
→ Furina: 我好崇拜你 07/15 14:10
→ DJYOMIYAHINA: 我好崇拜你 07/15 14:12
※ 引述 《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;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.32.223 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721023340.A.40E.html