Formatted question description: https://leetcode.ca/all/894.html

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/

// 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;
    }
};

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> allPossibleFBT(int N) {
        if (N % 2 == 0)
            return new ArrayList<TreeNode>();
        Map<Integer, List<TreeNode>> map = new HashMap<Integer, List<TreeNode>>();
        List<TreeNode> oneList = new ArrayList<TreeNode>();
        oneList.add(new TreeNode(0));
        map.put(1, oneList);
        for (int i = 3; i <= N; i += 2) {
            List<TreeNode> curList = map.getOrDefault(i, new ArrayList<TreeNode>());
            int sum = i - 1;
            for (int left = 1; left < sum; left++) {
                int right = sum - left;
                List<TreeNode> leftList = map.getOrDefault(left, new ArrayList<TreeNode>());
                List<TreeNode> rightList = map.getOrDefault(right, new ArrayList<TreeNode>());
                for (TreeNode leftNode : leftList) {
                    for (TreeNode rightNode : rightList) {
                        TreeNode root = new TreeNode(0);
                        root.left = leftNode;
                        root.right = rightNode;
                        curList.add(root);
                    }
                }
            }
            map.put(i, curList);
        }
        return map.get(N);
    }
}

All Problems

All Solutions