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.
The test cases will be generated such that the binary tree is valid.
因為 input 是亂序
我想不到不用 node buffer 的方式
首先會需要兩個 buffer
一個放所有 node
一個紀錄 node 是不是 child
接下來就是掃 input
建新的 node 塞進 buffer 或是從 buffer 撈存在的 node
然後根據 input 把 node 串起來
最後掃所有 node
不是 child 的那顆就是 root
/**
* 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) {}
* };
*/
class Solution {
public:
TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
map<int, TreeNode*> nodes;
map<int, int> parents;
for (vector<int>& d : descriptions) {
if (nodes.end() == nodes.find(d[0])) {
nodes[d[0]] = new TreeNode(d[0]);
}
if (nodes.end() == nodes.find(d[1])) {
nodes[d[1]] = new TreeNode(d[1]);
}
parents[d[1]] = d[0];
if (d[2]) {
nodes[d[0]]->left = nodes[d[1]];
}
else {
nodes[d[0]]->right = nodes[d[1]];
}
}
for (auto it = nodes.begin(); it != nodes.end(); it++) {
if (!parents[it->first]) {
return it->second;
}
}
return NULL;
}
};