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;
}
};