给你一个二维整数数组descriptions，其中descriptions[i] = [parenti, childi, isLefti]表示parenti是childi在二叉树中的父节点，二叉树中各节点的值互不相同。此外：
- 如果
isLefti == 1，那么childi就是parenti的左子节点。 - 如果
isLefti == 0，那么childi就是parenti的右子节点。
请你根据descriptions的描述来构造二叉树并返回其根节点。
测试用例会保证可以构造出有效的二叉树。
示例 1：
输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]输出：[50,20,80,15,17,19]解释：根节点是值为 50 的节点，因为它没有父节点。 结果二叉树如上图所示。
示例 2：
输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]输出：[1,2,null,null,3,4]解释：根节点是值为 1 的节点，因为它没有父节点。 结果二叉树如上图所示。
提示：
1 <= descriptions.length <= 10^4descriptions[i].length == 31 <= parenti, childi <= 10^50 <= isLefti <= 1descriptions所描述的二叉树是一棵有效二叉树
分析：首先确定根节点，即没有父节点的节点。可以用一个哈希表记录所有出现过的子节点。遍历 description 数组，标记所有 child。再遍历一次，找到第一个 parent 不在子节点集合中的节点，它就是根节点。
接着构建节点映射关系，用一个哈希表存储父节点对应的描述索引，便于快速找到父节点的所有子节点信息在 description 数组中的位置。
最后通过层次遍历构建二叉树。首先根节点进队，每次取出一个节点p，根据之前存储的父节点索引映射，找到当前节点 p 的值对应的所有 description 位置，根据 isLeft 决定挂在左孩子还是右孩子。如果子节点本身也是其他节点的父节点，则将其加入队列继续处理。
/** * 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) { int n=descriptions.size(); map<int,int>mp; map<int,vector<int>>mp_p,mp_c; for(int i=0;i<n;++i) mp_p[descriptions[i][0]].push_back(i),mp_c[descriptions[i][1]].push_back(i),mp[descriptions[i][1]]=1; int index=0,cnt=1,f=1; for(int i=0;i<n&&f;++i) if(mp[descriptions[i][0]]==0) index=i,f=0; TreeNode* root=(TreeNode*)malloc(sizeof(TreeNode));root->left=root->right=NULL; root->val=descriptions[index][0]; queue<TreeNode*>que;que.push(root); while(!que.empty()) { TreeNode *p=que.front();que.pop(); int len=mp_p[p->val].size(); for(int i=0;i<len;++i) { TreeNode *q=(TreeNode*)malloc(sizeof(TreeNode));;q->left=q->right=NULL; q->val=descriptions[mp_p[p->val][i]][1]; if(descriptions[mp_p[p->val][i]][2]==1) p->left=q; else p->right=q; if(mp_p[q->val].size())que.push(q); } } return root; } };
