<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>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        // todo: check if works without special case n = 1
        // and explain why we might actually need it
        if (n == 1)
        {
            return {new TreeNode};
        }
        else if (n % 2 == 0)
        {
            return {};
        }
        
        const auto seqs = formChoiceSeqs(n);
        
        std::vector<TreeNode*> result = std::vector<TreeNode*>(seqs.size());
        for (int i = 0; i < seqs.size(); ++i)
        {
            result[i] = new TreeNode;
            auto leaves = std::vector<TreeNode*>{result[i]};
            for (const auto choice: seqs[i])
            {
                leaves[choice]->left = new TreeNode;
                leaves[choice]->right = new TreeNode;
                
                leaves.insert(leaves.begin() + choice + 1, leaves[choice]->right);
                leaves[choice] = leaves[choice]->left;
            }
        }

        return result;
    }

    std::vector<std::vector<int>> formChoiceSeqs(int n)
    {
        // n is the number of nodes in each resulting
        // with every 2 nodes added to a leaf (number added to a seq) n decreases by 2
        // length of seq = (n-1)/2
        // form every possible sequence where every next number is >= prev number and
        // every number is <= its position in the seq
        // every seq will start by 0, because we start adding numbers after we
        // already have a root established and we have the only choice of 0
        std::vector<std::vector<int>> seqs = {{0}};
        for (int newLength = 2; newLength <= (n-1)/2; ++newLength)
        {
            seqs = extendSeqsBy1(seqs, newLength);
        }

        return seqs;
    }

    std::vector<std::vector<int>> extendSeqsBy1(std::vector<std::vector<int>>& seqs, int newLength)
    {
        std::vector<std::vector<int>> result;
        for (const auto seq: seqs)
        {
            for (int newEl = *seq.crbegin(); newEl < newLength; ++newEl)
            {
                auto temp = seq;
                temp.emplace_back(newEl);
                result.emplace_back(temp);
            }
        }

        return result;
    }

    // if n == 1, it's just root
    // n can't be 2 or any even number, but can be any odd number
    // there is a procedure of forming a tree - add 2 new leaves to a leaf
    // on every step we make a choice among k leaves
    // k++ on every step because one leaf goes away, 2 new leaves emerge
    // 1. forms a valid full bin tree
    // 2. can form every tree
    // mark leaves with numbers from left to right
    // every distinct set of choices forms a distinct tree? no
    // only distinct trees matter, so how can we optimize
    // additional rule of first choosing a smaller number? i.e. filling the tree from left to right
    // i.e. if we add to leaf m, we never add to leaves < m
    // 1. now distinct choices form distinct trees
    // 2. we did not remove any trees from the result
};
43188