{"id":3675,"date":"2018-08-23T01:08:39","date_gmt":"2018-08-23T08:08:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3675"},"modified":"2018-08-24T21:31:51","modified_gmt":"2018-08-25T04:31:51","slug":"leetcode-889-construct-binary-tree-from-preorder-and-postorder-traversal","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-889-construct-binary-tree-from-preorder-and-postorder-traversal\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal - \u5237\u9898\u627e\u5de5\u4f5c EP219\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/53aOi0Drp9I?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Return any binary tree that matches the given preorder and postorder traversals.<\/p>\n<p>Values in the traversals\u00a0<code>pre<\/code>\u00a0and\u00a0<code>post<\/code>\u00a0are distinct\u00a0positive integers.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>pre = <span id=\"example-input-1-1\">[1,2,4,5,3,6,7]<\/span>, post = <span id=\"example-input-1-2\">[4,5,2,6,7,3,1]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">[1,2,3,4,5,6,7]<\/span>\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>1 &lt;= pre.length == post.length &lt;= 30<\/code><\/li>\n<li><code>pre[]<\/code>\u00a0and\u00a0<code>post[]<\/code>\u00a0are both permutations of\u00a0<code>1, 2, ..., pre.length<\/code>.<\/li>\n<li>It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.<\/li>\n<\/ul>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3688\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/889-ep219.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/889-ep219.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/889-ep219-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/889-ep219-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution: Recursion<\/strong><\/h1>\n<p>pre = [(root) (left-child) (right-child)]<\/p>\n<p>post = [(left-child) (right-child) (root)]<\/p>\n<p>We need to recursively find the first node in pre.left-child from post.left-child<\/p>\n<p>e.g.<\/p>\n<p><span id=\"example-input-1-1\">pre = [(<span style=\"color: #0000ff;\"><strong>1<\/strong><\/span>), (<span style=\"color: #ff0000;\"><strong>2<\/strong><\/span>,4,5), (3,6,7)]<\/span><\/p>\n<p>post =\u00a0<span id=\"example-input-1-2\">[(4,5,<strong><span style=\"color: #ff0000;\">2<\/span><\/strong>), (6,7,3), (<span style=\"color: #0000ff;\"><strong>1<\/strong><\/span>)]<\/span><\/p>\n<p>First element of left-child is 2 and the length of it is 3.<\/p>\n<p>root = new TreeNode(1)<br \/>\nroot.left = build((2,4,5), (4,5,2))<br \/>\nroot.right = build((3,6,7), (6,7,3))<\/p>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(n)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 8 ms\r\nclass Solution {\r\npublic:\r\n  TreeNode* constructFromPrePost(vector&lt;int&gt;&amp; pre, vector&lt;int&gt;&amp; post) {\r\n    return constructFromPrePost(cbegin(pre), cend(pre), cbegin(post), cend(post));\r\n  }\r\nprivate:\r\n  typedef vector&lt;int&gt;::const_iterator VIT;\r\n  TreeNode* constructFromPrePost(VIT pre_l, VIT pre_r, VIT post_l, VIT post_r) {\r\n    if (pre_l == pre_r) return nullptr;\r\n    TreeNode* root = new TreeNode(*pre_l);\r\n    ++pre_l;\r\n    --post_r;\r\n    if (pre_l == pre_r) return root;\r\n    VIT post_m = next(find(post_l, post_r, *pre_l));\r\n    VIT pre_m = pre_l + (post_m - post_l);\r\n    root-&gt;left = constructFromPrePost(pre_l, pre_m, post_l, post_m);\r\n    root-&gt;right = constructFromPrePost(pre_m, pre_r, post_m, post_r);\r\n    return root;\r\n  }\r\n};<\/pre>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(n)<\/p>\n<pre class=\"lang:python decode:true\">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 60 ms\r\n\"\"\"\r\nclass Solution:\r\n  def constructFromPrePost(self, pre, post):\r\n    def build(i, j, n):\r\n      if n &lt;= 0: return None\r\n      root = TreeNode(pre[i])\r\n      if n == 1: return root\r\n      k = j      \r\n      while post[k] != pre[i + 1]: k += 1\r\n      l = k - j + 1      \r\n      root.left = build(i + 1, j, l)\r\n      root.right = build(i + l + 1, k + 1, n - l - 1)\r\n      return root\r\n    return build(0, 0, len(pre))<\/pre>\n<p>Time complexity: O(n)<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 52 ms (beats 100%)\r\n\"\"\"\r\nclass Solution:\r\n  def constructFromPrePost(self, pre, post):    \r\n    def build(i, j, n):\r\n      if n &lt;= 0: return None\r\n      root = TreeNode(pre[i])\r\n      if n == 1: return root\r\n      k = index[pre[i + 1]]      \r\n      l = k - j + 1      \r\n      root.left = build(i + 1, j, l)\r\n      root.right = build(i + l + 1, k + 1, n - l - 1)\r\n      return root\r\n    index = {}\r\n    for i in range(len(pre)):\r\n      index[post[i]] = i\r\n    return build(0, 0, len(pre))<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Return any binary tree that matches the given preorder and postorder traversals. Values in the traversals\u00a0pre\u00a0and\u00a0post\u00a0are distinct\u00a0positive integers. Example 1: Input: pre = [1,2,4,5,3,6,7],&#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":[56,57,385,32,28],"class_list":["post-3675","post","type-post","status-publish","format-standard","hentry","category-tree","tag-postorder","tag-preorder","tag-reconstruct","tag-traversal","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3675","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=3675"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3675\/revisions"}],"predecessor-version":[{"id":3689,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3675\/revisions\/3689"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3675"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3675"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3675"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}