{"id":5705,"date":"2019-10-03T09:03:28","date_gmt":"2019-10-03T16:03:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5705"},"modified":"2019-10-03T09:03:38","modified_gmt":"2019-10-03T16:03:38","slug":"leetcode-105-construct-binary-tree-from-preorder-and-inorder-traversal","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-105-construct-binary-tree-from-preorder-and-inorder-traversal\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal"},"content":{"rendered":"\n<p>Given preorder and inorder traversal of a tree, construct the binary tree.<\/p>\n\n\n\n<p><strong>Note:<\/strong><br>You may assume that duplicates do not exist in the tree.<\/p>\n\n\n\n<p>For example, given<\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">preorder =&nbsp;[3,9,20,15,7]\ninorder = [9,3,15,20,7]<\/pre>\n\n\n\n<p>Return the following binary tree:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">    3\n   \/ \\\n  9  20\n    \/  \\\n   15   7<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Recursion<\/strong><\/h2>\n\n\n\n<p>Preprocessing: use a hashtable to store the index of element in preorder array.<\/p>\n\n\n\n<p>For an element in inorder array, find the pos of it in preorder array in O(1), anything to the left will be the leftchild and anything to the right will be the right child.<\/p>\n\n\n\n<p>e.g. <br>buildTree([9, 3, 15, 20, 7], [3, 9, 20, 15, 7]):  <br>  root = TreeNode(9) # inorder[0] = 9 <br>  root.left = buildTree([3], [3])<br>  root.right = buildTree([15, 20, 7], [20, 15, 7])<br>  return root<\/p>\n\n\n\n<p><\/p>\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 *buildTree(vector<int> &preorder, vector<int> &inorder) {\n    unordered_map<int, int> pos;\n\n    for (int i = 0; i < inorder.size(); i++)\n      pos[inorder[i]] = i;\n\n    function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {\n      if (ps > pe) return (TreeNode*)nullptr;\n\n      int im = pos[preorder[ps]];\n      int pm = ps + (im - is);\n\n      auto root = new TreeNode(preorder[ps]);\n      root->left  = buildTree(is, im - 1, ps + 1, pm);\n      root->right = buildTree(im + 1, ie, pm + 1, pe);\n      return root;\n    };\n\n    return buildTree(0, inorder.size() - 1, 0, preorder.size() - 1);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Related Problems<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1008-construct-binary-search-tree-from-preorder-traversal\/\">https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1008-construct-binary-search-tree-from-preorder-traversal\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-889-construct-binary-tree-from-preorder-and-postorder-traversal\/\">https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-889-construct-binary-tree-from-preorder-and-postorder-traversal\/<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Given preorder and inorder traversal of a tree, construct the binary tree. Note:You may assume that duplicates do not exist in the tree. For example,&#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":[457,82,376,17,28],"class_list":["post-5705","post","type-post","status-publish","format-standard","hentry","category-tree","tag-construct","tag-hashtable","tag-on","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5705","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=5705"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5705\/revisions"}],"predecessor-version":[{"id":5707,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5705\/revisions\/5707"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5705"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5705"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5705"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}