{"id":3695,"date":"2018-08-26T00:07:50","date_gmt":"2018-08-26T07:07:50","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3695"},"modified":"2018-08-30T13:37:49","modified_gmt":"2018-08-30T20:37:49","slug":"leetcode-894-all-possible-full-binary-trees","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-894-all-possible-full-binary-trees\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 894. All Possible Full Binary Trees"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 894. All Possible Full Binary Trees - \u5237\u9898\u627e\u5de5\u4f5c EP221\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/noVVstnQvyY?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>Problem<\/h1>\n<p>A\u00a0<em>full binary tree<\/em>\u00a0is a binary tree where each node has exactly 0 or 2\u00a0children.<\/p>\n<p>Return a list of all possible full binary trees with\u00a0<code>N<\/code>\u00a0nodes.\u00a0 Each element of the answer is the root node of one possible tree.<\/p>\n<p>Each\u00a0<code>node<\/code>\u00a0of each\u00a0tree in the answer\u00a0<strong>must<\/strong>\u00a0have\u00a0<code>node.val = 0<\/code>.<\/p>\n<p>You may return the final list of trees in any order.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">7<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]<\/span>\r\n<strong>Explanation:<\/strong>\r\n<img decoding=\"async\" src=\"https:\/\/s3-lc-upload.s3.amazonaws.com\/uploads\/2018\/08\/22\/fivetrees.png\" alt=\"\" \/>\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>1 &lt;= N &lt;= 20<\/code><\/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\">\u00a0<\/ins><\/p>\n<h1><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3734\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/894-ep221.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/894-ep221.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/894-ep221-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/894-ep221-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/h1>\n<h1><strong>Solution: Recursion<\/strong><\/h1>\n<p>Key observations:<\/p>\n<ol>\n<li>n must be odd, If n is even, no possible trees<\/li>\n<li>ans is the cartesian product of trees(i) and trees(n-i-1). Ans = {Tree(0, l, r) for l, r in trees(i) X trees(N &#8211; i &#8211; 1)}.<\/li>\n<\/ol>\n<p>w\/o cache<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 72 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;TreeNode*&gt; allPossibleFBT(int N) {\r\n    if (N % 2 == 0) return {};\r\n    if (N == 1) return {new TreeNode(0)};\r\n    vector&lt;TreeNode*&gt; ans;\r\n    for (int i = 1; i &lt; N; i += 2) {      \r\n      for (const auto&amp; l : allPossibleFBT(i))\r\n        for (const auto&amp; r : allPossibleFBT(N - i - 1)) {\r\n          auto root = new TreeNode(0);\r\n          root-&gt;left = l;\r\n          root-&gt;right = r;\r\n          ans.push_back(root);\r\n        }    \r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 20 ms\r\nclass Solution {\r\n  public List&lt;TreeNode&gt; allPossibleFBT(int N) {\r\n    List&lt;TreeNode&gt; ans = new ArrayList&lt;&gt;();\r\n    if (N % 2 == 0) return ans;\r\n    if (N == 1) {\r\n      ans.add(new TreeNode(0));\r\n      return ans;\r\n    }\r\n    for (int i = 1; i &lt; N; i += 2) {\r\n      for (TreeNode l : allPossibleFBT(i))\r\n        for (TreeNode r : allPossibleFBT(N - i - 1)) {\r\n          TreeNode root = new TreeNode(0);\r\n          root.left = l;\r\n          root.right = r;\r\n          ans.add(root);\r\n        }          \r\n    }\r\n    return ans;\r\n  }<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 396 ms\r\n\"\"\"\r\nclass Solution:\r\n  def allPossibleFBT(self, N):\r\n    if N % 2 == 0: return []\r\n    if N == 1: return [TreeNode(0)]\r\n    ans = []\r\n    for i in range(1, N, 2):\r\n      for l in self.allPossibleFBT(i):\r\n        for r in self.allPossibleFBT(N - i - 1):\r\n          root = TreeNode(0)\r\n          root.left = l\r\n          root.right = r\r\n          ans.append(root)\r\n    return ans<\/pre>\n<\/div><\/div>\n<p>w\/cache<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 68 ms\r\nstatic constexpr int kMaxN = 20 + 1;\r\nstatic array&lt;vector&lt;TreeNode*&gt;, kMaxN&gt; m;\r\n\r\nclass Solution {\r\npublic:\r\n  vector&lt;TreeNode*&gt; allPossibleFBT(int N) {\r\n    return trees(N);\r\n  }\r\nprivate:\r\n  vector&lt;TreeNode*&gt;&amp; trees(int N) {\r\n    if (m[N].size() &gt; 0) return m[N];\r\n    vector&lt;TreeNode*&gt;&amp; ans = m[N];\r\n    if (N % 2 == 0) return ans = {};    \r\n    if (N == 1) ans = {new TreeNode(0)};\r\n    for (int i = 1; i &lt; N; i += 2) {\r\n      for (const auto&amp; l : trees(i))\r\n        for (const auto&amp; r : trees(N - i - 1)) {\r\n          auto root = new TreeNode(0);\r\n          root-&gt;left = l;\r\n          root-&gt;right = r;\r\n          ans.push_back(root);\r\n        }    \r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<p>using itertools.product w\/ cache<\/p>\n<pre class=\"lang:python decode:true\">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 188 ms\r\n\"\"\"\r\nm = [[] for _ in range(21)]\r\nclass Solution:\r\n  def allPossibleFBT(self, N):\r\n    if N % 2 == 0: return []\r\n    if N == 1: return [TreeNode(0)]\r\n    if len(m[N]) &gt; 0: return m[N]\r\n    ans = []\r\n    for i in range(1, N, 2):\r\n      for l, r in itertools.product(self.allPossibleFBT(i), \r\n                                    self.allPossibleFBT(N - i - 1)):      \r\n        root = TreeNode(0)\r\n        root.left = l\r\n        root.right = r\r\n        ans.append(root)\r\n    m[N] = ans\r\n    return ans<\/pre>\n<\/div><\/div>\n<p>DP<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 100 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;TreeNode*&gt; allPossibleFBT(int N) {\r\n    if (N % 2 == 0) return {};\r\n    vector&lt;vector&lt;TreeNode*&gt;&gt; dp(N + 1);\r\n    dp[1] = {new TreeNode(0)};\r\n    for (int i = 3; i &lt;= N; i += 2)\r\n      for (int j = 1; j &lt; i; j += 2) {\r\n        int k = i - j - 1;\r\n        for (const auto&amp; l : dp[j])\r\n          for (const auto&amp; r : dp[k]) {\r\n            auto root = new TreeNode(0);\r\n            root-&gt;left = l;\r\n            root-&gt;right = r;\r\n            dp[i].push_back(root);\r\n          }            \r\n      }\r\n      return dp[N];\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Benchmark<\/strong><\/h1>\n<p>No-cache vs cached<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3738\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/894-ep221-cpu.png\" alt=\"\" width=\"600\" height=\"371\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/894-ep221-cpu.png 600w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/894-ep221-cpu-300x186.png 300w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">#include &lt;iostream&gt;\r\n#include &lt;vector&gt;\r\n#include &lt;array&gt;\r\n#include &lt;ctime&gt;\r\n#include &lt;cstdio&gt;\r\nusing namespace std;\r\n\r\nstruct TreeNode {\r\n  int val;\r\n  TreeNode *left;\r\n  TreeNode *right;\r\n  TreeNode(int x) : val(x), left(NULL), right(NULL) {}\r\n};\r\n\r\nstatic constexpr int kMaxN = 101 + 1;\r\nstatic array&lt;vector&lt;TreeNode*&gt;, kMaxN&gt; m;\r\n\r\nclass NoCache {\r\npublic:\r\n  vector&lt;TreeNode*&gt; allPossibleFBT(int N) {\r\n    if (N % 2 == 0) return {};\r\n    if (N == 1) return {new TreeNode(0)};\r\n    vector&lt;TreeNode*&gt; ans;\r\n    for (int i = 1; i &lt; N; i += 2) {\r\n      for (const auto&amp; l : allPossibleFBT(i))\r\n        for (const auto&amp; r : allPossibleFBT(N - i - 1)) {\r\n          auto root = new TreeNode(0);\r\n          root-&gt;left = l;\r\n          root-&gt;right = r;\r\n          ans.push_back(root);\r\n        }    \r\n    }\r\n    return ans;\r\n  }\r\n};\r\n\r\nclass Cached {\r\npublic:\r\n  vector&lt;TreeNode*&gt; allPossibleFBT(int N) {\r\n    return trees(N);\r\n  }\r\nprivate:\r\n  vector&lt;TreeNode*&gt;&amp; trees(int N) {\r\n    if (m[N].size() &gt; 0) return m[N];\r\n    vector&lt;TreeNode*&gt;&amp; ans = m[N];\r\n    if (N % 2 == 0) return ans = {};\r\n    if (N == 1) ans = {new TreeNode(0)};\r\n    for (int i = 1; i &lt; N; i += 2) {\r\n      for (const auto&amp; l : trees(i))\r\n        for (const auto&amp; r : trees(N - i - 1)) {\r\n          auto root = new TreeNode(0);\r\n          root-&gt;left = l;\r\n          root-&gt;right = r;\r\n          ans.push_back(root);\r\n        }    \r\n    }\r\n    return ans;\r\n  }\r\n};\r\n\r\nint main(int argc, char** argv) {\r\n  printf(\"N\\tno-cache\\tcached\\n\");\r\n  for (int i = 1; i &lt;= 35; i += 2) {\r\n    printf(\"%02d\\t\", i);\r\n    {\r\n      auto start = clock();\r\n      (void)(NoCache().allPossibleFBT(i));\r\n      printf(\"%8.4f\\t\", static_cast&lt;double&gt;(clock() - start) \/ CLOCKS_PER_SEC);\r\n    }\r\n    {\r\n      \/\/ Clear the cache.\r\n      for (int j = 0; j &lt; kMaxN; ++j)\r\n        m[i].clear();\r\n      auto start = clock();\r\n      (void)(Cached().allPossibleFBT(i));\r\n      printf(\"%8.4f\\n\", static_cast&lt;double&gt;(clock() - start) \/ CLOCKS_PER_SEC);\r\n    }\r\n  }\r\n  return 0;\r\n}<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem A\u00a0full binary tree\u00a0is a binary tree where each node has exactly 0 or 2\u00a0children. Return a list of all possible full binary trees with\u00a0N\u00a0nodes.\u00a0&#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":[18,177,17,28],"class_list":["post-3695","post","type-post","status-publish","format-standard","hentry","category-tree","tag-dp","tag-medium","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3695","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=3695"}],"version-history":[{"count":14,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3695\/revisions"}],"predecessor-version":[{"id":3697,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3695\/revisions\/3697"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3695"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3695"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3695"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}