【算法模板】满二叉树生成

例题：所有可能的真二叉树

以力扣面试题 894题为例：

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

---

    Map<Integer, List<TreeNode>> memo = new HashMap();
    public List<TreeNode> allPossibleFBT_leetcode(int N) {
        if (!memo.containsKey(N)) {
            List<TreeNode> ans = new LinkedList();
            // 满二叉树的节点数量都是奇数
            if (N == 1) {
                ans.add(new TreeNode(0));
            } else if (N % 2 == 1) {
                for (int x = 0; x < N; ++x) {
                    // 某个节点下的左右子树节点数量==N-1
                    // 左子树节点数为x，右子树节点数为y，x和y都应该是奇数
                    // 因此else if (N % 2 == 1)是为了避免allPossibleFBT(x)、allPossibleFBT(y)出现错误的结果
                    // 即当x、y为偶数时，返回的List<TreeNode>，其大小为0，那么会进入下个循环
                    int y = N - 1 - x;
                    for (TreeNode left : allPossibleFBT(x)) {
                        for (TreeNode right : allPossibleFBT(y)) {
                            TreeNode bns = new TreeNode(0);
                            bns.left = left;
                            bns.right = right;
                            ans.add(bns);
                        }
                    }
                }
            }
            memo.put(N, ans);
        }
        // memo缓存数量为N的满二叉树，避免再次递归，节约时间
        return memo.get(N);
    }