<p>Given an integer <code>n</code>, return <em>a list of all possible <strong>full binary trees</strong> with</em> <code>n</code> <em>nodes</em>. Each node of each tree in the answer must have <code>Node.val == 0</code>.</p>

<p>Each element of the answer is the root node of one possible tree. You may return the final list of trees in <strong>any order</strong>.</p>

<p>A <strong>full binary tree</strong> is a binary tree where each node has exactly <code>0</code> or <code>2</code> children.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/22/fivetrees.png" style="width: 700px; height: 400px;" />
<pre>
<strong>Input:</strong> n = 7
<strong>Output:</strong> [[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]]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> [[0,0,0]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 20</code></li>
</ul>

class Solution {
public:
  TreeNode* clone(TreeNode* root) {
    TreeNode* new_root = new TreeNode(0);
    new_root->left = (root->left) ? clone(root->left) : nullptr;
    new_root->right = (root->right) ? clone(root->right) : nullptr; 
    return new_root;
  } 

  vector<TreeNode*> allPossibleFBT(int N) {
    if (0 == N % 2) {
      return std::vector<TreeNode*>{};
    } else if (1 == N) {
      return std::vector<TreeNode*>{1, new TreeNode{0}};
    }

    // For each level, holds all the patterns for all the full BST
    std::vector<std::vector<TreeNode>> patterns;
    patterns.emplace_back();
    patterns.back().emplace_back(0);

    // Build up a pattern for all the balanaced trees using n - 2 nodes. Note that the patterns are 
    // deliberately linked together for efficency. It is not safe to return this, a full clone of
    // each pattern will be required
    for (int root = 1; root < N / 2; ++root) {
      patterns.emplace_back();
      for (int left_size = 0; left_size < root; ++left_size) {
        for (auto& left : patterns[left_size]) {
          for (auto& right : patterns[root - left_size - 1]) {
            patterns.back().emplace_back(0);
            patterns.back().back().left = &left;
            patterns.back().back().right = &right;
          }
        }
      }
    }

    // Final level should actually create a tree that can be returned from the patterns generate above
    std::vector<TreeNode*> ret;
    for (int root = 0; root < N / 2; ++root) {
      for (auto& left : patterns[root]) {
        for (auto& right : patterns[N / 2 - root - 1]) {
          ret.emplace_back(new TreeNode(0));
          ret.back()->left = clone(&left);
          ret.back()->right = clone(&right);
        }
      }
    }

    return ret;
  }
};
38643