All Possible Full Binary Trees

https://leetcode.com/problems/all-possible-full-binary-trees/description/

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

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

Eachnodeof each tree in the answermusthavenode.val = 0.

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

Thougts

看到这种所有可能的树的问题应该想到把树分成左右两只。两只的各种可能情况的组合就是答案。让FBT(N) be the list of all possible full binary trees with N nodes，因为是full tree, N只能是奇数，设FBT(x)为左子树有x个节点时的所有可能情况，那么右子树所有可能情况即FBT(N - x -1). 再两个循环把左子树情况和右子树情况做个笛卡尔积就可以了。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, List<TreeNode>> cache = new HashMap<>();

    public List<TreeNode> allPossibleFBT(int N) {
        if (cache.containsKey(N)) {
            return cache.get(N);
        }
        List<TreeNode> res = new ArrayList<>();
        if (N == 1) {
            res.add(new TreeNode(0));
        } else if ((N & 1) == 1) {
            for (int x = 1; x < N; x++) {
                int y = N - x - 1;
                for (TreeNode left : allPossibleFBT(x)) {
                    for (TreeNode right : allPossibleFBT(y)) {
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        res.add(root);
                    }
                }
            }
        }

        return res;
    }
}

Analysis

https://leetcode.com/problems/all-possible-full-binary-trees/solution/

总数目是个卡特兰数，O(2^N).