{"id":9558,"date":"2022-03-08T03:58:52","date_gmt":"2022-03-08T11:58:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9558"},"modified":"2022-03-08T04:01:58","modified_gmt":"2022-03-08T12:01:58","slug":"leetcode-2196-create-binary-tree-from-descriptions","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-2196-create-binary-tree-from-descriptions\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2196. Create Binary Tree From Descriptions"},"content":{"rendered":"\n<p>You are given a 2D integer array&nbsp;<code>descriptions<\/code>&nbsp;where&nbsp;<code>descriptions[i] = [parent<sub>i<\/sub>, child<sub>i<\/sub>, isLeft<sub>i<\/sub>]<\/code>&nbsp;indicates that&nbsp;<code>parent<sub>i<\/sub><\/code>&nbsp;is the&nbsp;<strong>parent<\/strong>&nbsp;of&nbsp;<code>child<sub>i<\/sub><\/code>&nbsp;in a&nbsp;<strong>binary<\/strong>&nbsp;tree of&nbsp;<strong>unique<\/strong>&nbsp;values. Furthermore,<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If&nbsp;<code>isLeft<sub>i<\/sub>&nbsp;== 1<\/code>, then&nbsp;<code>child<sub>i<\/sub><\/code>&nbsp;is the left child of&nbsp;<code>parent<sub>i<\/sub><\/code>.<\/li><li>If&nbsp;<code>isLeft<sub>i<\/sub>&nbsp;== 0<\/code>, then&nbsp;<code>child<sub>i<\/sub><\/code>&nbsp;is the right child of&nbsp;<code>parent<sub>i<\/sub><\/code>.<\/li><\/ul>\n\n\n\n<p>Construct the binary tree described by&nbsp;<code>descriptions<\/code>&nbsp;and return&nbsp;<em>its&nbsp;<strong>root<\/strong><\/em>.<\/p>\n\n\n\n<p>The test cases will be generated such that the binary tree is&nbsp;<strong>valid<\/strong>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2022\/02\/09\/example1drawio.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]\n<strong>Output:<\/strong> [50,20,80,15,17,19]\n<strong>Explanation:<\/strong> The root node is the node with value 50 since it has no parent.\nThe resulting binary tree is shown in the diagram.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2022\/02\/09\/example2drawio.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> descriptions = [[1,2,1],[2,3,0],[3,4,1]]\n<strong>Output:<\/strong> [1,2,null,null,3,4]\n<strong>Explanation:<\/strong> The root node is the node with value 1 since it has no parent.\nThe resulting binary tree is shown in the diagram.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= descriptions.length &lt;= 10<sup>4<\/sup><\/code><\/li><li><code>descriptions[i].length == 3<\/code><\/li><li><code>1 &lt;= parent<sub>i<\/sub>, child<sub>i<\/sub>&nbsp;&lt;= 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= isLeft<sub>i<\/sub>&nbsp;&lt;= 1<\/code><\/li><li>The binary tree described by&nbsp;<code>descriptions<\/code>&nbsp;is valid.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Hashtable + Recursion<\/strong><\/h2>\n\n\n\n<ol class=\"wp-block-list\"><li>Use one hashtable to track the children of each node.<\/li><li>Use another hashtable to track the parent of each node.<\/li><li>Find the root who doesn&#8217;t have parent.<\/li><li>Build the tree recursively from root.<br><\/li><\/ol>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {\n    unordered_set<int> hasParent;\n    unordered_map<int, pair<int, int>> children;\n    for (const auto& d : descriptions) {\n      hasParent.insert(d[1]);\n      (d[2] ? children[d[0]].first : children[d[0]].second) = d[1];      \n    }\n    int root = -1;\n    for (const auto& d : descriptions)\n      if (!hasParent.count(d[0])) root = d[0];\n    function<TreeNode*(int)> build = [&](int cur) -> TreeNode* {      \n      if (!cur) return nullptr;\n      return new TreeNode(cur, \n                          build(children[cur].first),\n                          build(children[cur].second));\n    };  \n    return build(root);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a 2D integer array&nbsp;descriptions&nbsp;where&nbsp;descriptions[i] = [parenti, childi, isLefti]&nbsp;indicates that&nbsp;parenti&nbsp;is the&nbsp;parent&nbsp;of&nbsp;childi&nbsp;in a&nbsp;binary&nbsp;tree of&nbsp;unique&nbsp;values. Furthermore, If&nbsp;isLefti&nbsp;== 1, then&nbsp;childi&nbsp;is the left child of&nbsp;parenti. If&nbsp;isLefti&nbsp;== 0,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[82,177,17,28],"class_list":["post-9558","post","type-post","status-publish","format-standard","hentry","category-tree","tag-hashtable","tag-medium","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9558","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9558"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9558\/revisions"}],"predecessor-version":[{"id":9560,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9558\/revisions\/9560"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9558"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9558"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9558"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}