894 所有可能的真二叉树

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

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

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

感觉很像之前写过的一道题

记忆化搜索

由分析知道，n不能为偶数，叶子节点为（n+1）/2，度为二的节点为(n-1)/2，n=1的时候就只有一个节点，n可以拆分出[x,1,y]三个，x和y都必须是奇数，x和y都比n小而且一定在之前的遍历中已经计算过，只要深拷贝n=x和n=y的数组，作为左边右边，就可以得到最终答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //记忆化保存的数组
    List<List<TreeNode>> list = new ArrayList<>();
    List<TreeNode> treeNodeList;
    public List<TreeNode> allPossibleFBT(int n) {
        //排除偶数
        if (n%2==0){
            return new ArrayList<>();
        }
        treeNodeList = new ArrayList<>();
        treeNodeList.add(new TreeNode(0));
        list.add(treeNodeList);
        for (int k = 3; k <= n; k+=2) {
            treeNodeList = new ArrayList<>();
            for (int i = 1; i < k-1; i+=2) {
                //System.out.println(i);
                //由于i是+=2的，对应的list下标是++，所以要/2
                List<TreeNode> left = new ArrayList<>(list.get(i/2));
                List<TreeNode> right = new ArrayList<>(list.get((k-1-i)/2));
                for (int p = 0; p < left.size(); p++) {
                    for (int q = 0; q < right.size(); q++) {
                        TreeNode root = new TreeNode(0);
                        root.left = left.get(p);
                        root.right = right.get(q);
                        //先保存到treenodeList里
                        treeNodeList.add(root);
                    }
                }
            }
            //System.out.println(treeNodeList.size());
            //最后加上这个
            list.add(treeNodeList);
        }
        //System.out.println(list.get(n/2).size());
        //返回记忆化搜索最后一个
        return list.get(n/2);

    }
}