题目：所有可能的满二叉树
class Solution { public List<TreeNode> allPossibleFBT(int N) { List<TreeNode> list = new ArrayList<>(); //N必须是奇数的，偶数无法构造满二叉树 if (N % 2 == 0){ return list; } //递归跳出条件，只有一个，不能再分了 if (N == 1) { ArrayList<TreeNode> down = new ArrayList<>(); down.add(new TreeNode(0)); return down; } /* 比如题目的N=7，那么可以分为 1、【1(左子树),1(头结点),5(右子树)】 2、【2(左子树),1(头结点),4(右子树)】 3、【3(左子树),1(头结点),3(右子树)】 4、【4(左子树),1(头结点),2(右子树)】 5、【5(左子树),1(头结点),1(右子树)】 但是，很明显第2、4种是不行的，因为出现了偶数，所以只有 1、【1(左子树),1(头结点),5(右子树)】 3、【3(左子树),1(头结点),3(右子树)】 5、【5(左子树),1(头结点),1(右子树)】 这时候你可能纳闷，只有3种,那答案为什么是5种呢？ 其实，可以发现1、【1(左子树),1(头结点),5(右子树)】 与 5、【5(左子树),1(头结点),1(右子树)】 各有两种摆法，这时候又要重复上面的步骤了（递归） ---所以这题要用递归求解 */ for (int i = 1; i < N; i++) { List<TreeNode> list1 = allPossibleFBT(i); List<TreeNode> list2 = allPossibleFBT(N - i - 1); //-1是因为要父结点留个位置 /* 如何理解这两个for呢？ 比如说现在需要摆七个，并且我选择了 【1(左子树),1(头结点),5(右子树)】的摆法 其中5(右子树)有两种摆法。这两种摆法就加入了list2里头，然后list1只有一种摆法(因为只有一个) 然后对list1和list2里面的头结点进行排列组合即可（共两种） */ for (TreeNode left : list1) { for (TreeNode right : list2) { TreeNode father = new TreeNode(0); father.left = left; father.right = right; list.add(father); } } } return list; } }