894

894. All Possible Full Binary Trees (Medium)

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

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

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

 

Example 1:

Input: n = 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]]

Example 2:

Input: n = 3
Output: [[0,0,0]]

 

Constraints:

• 1 <= n <= 20

Companies: Adobe, Amazon, Google

Related Topics:
Dynamic Programming, Tree, Recursion, Memoization, Binary Tree

Solution 1.

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