leetcode 2196. 根据描述创建二叉树 中等

给你一个二维整数数组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(vectorvectorint descriptions) { int ndescriptions.size(); mapint,intmp; mapint,vectorintmp_p,mp_c; for(int i0;in;i) mp_p[descriptions[i][0]].push_back(i),mp_c[descriptions[i][1]].push_back(i),mp[descriptions[i][1]]1; int index0,cnt1,f1; for(int i0;inf;i) if(mp[descriptions[i][0]]0) indexi,f0; TreeNode* root(TreeNode*)malloc(sizeof(TreeNode));root-leftroot-rightNULL; root-valdescriptions[index][0]; queueTreeNode*que;que.push(root); while(!que.empty()) { TreeNode *pque.front();que.pop(); int lenmp_p[p-val].size(); for(int i0;ilen;i) { TreeNode *q(TreeNode*)malloc(sizeof(TreeNode));;q-leftq-rightNULL; q-valdescriptions[mp_p[p-val][i]][1]; if(descriptions[mp_p[p-val][i]][2]1) p-leftq; else p-rightq; if(mp_p[q-val].size())que.push(q); } } return root; } };