894. All Possible Full Binary Trees

894. All Possible Full Binary Trees (Medium)

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes.  Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

 

Example 1:

Input: 7
Output: [[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]]
Explanation:

 

Note:

• 1 <= N <= 20

Companies:
Google

Related Topics:
Tree, Recursion

Solution 1.

// OJ: https://leetcode.com/problems/all-possible-full-binary-trees/
// Author: github.com/lzl124631x
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        if (N % 2 == 0) return {};
        if (N == 1) return { new TreeNode(0) };
        vector<TreeNode*> ans;
        for (int i = 1; i <= N - 2; i += 2) {
            auto lefts = allPossibleFBT(i);
            auto rights = allPossibleFBT(N - i - 1);
            for (auto left : lefts) {
                for (auto right : rights) {
                    auto root = new TreeNode(0);
                    root->left = left;
                    root->right = right;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
};