/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 给定节点数量，返回所有可能的树的集合（每棵树即节点的排兵布阵）
     *
     * @param N 当前树所有节点数
     * @return 返回树的根节点列表
     */
    public List<TreeNode> allPossibleFBT(int nodeCnt) {
        List<TreeNode> treeNodeList = new ArrayList<>();
        // 如果是偶数返回空，如果是1返回1个节点的列表
        /*
         * 1. if N = 3 , the number of nodes combination are as follows
         *       left    root    right
         *        1       1        1
         * --------------N = 3, res = 1----------
         * 2. if N = 5 , the number of nodes combination are as follows
         *       left    root    right
         *        1       1        3 (recursion)
         *        3       1        1
         *   --------------N = 5, res = 1 + 1 = 2----------
         * 3. if N = 7 , the number of nodes combination are as follows
         *       left    root    right
         *        1       1        5 (recursion)
         *        3       1        3
         *        5       1        1
         *   --------------N = 7, res = 2 + 1 + 2 = 5----------
         * 4. in order to make full binary tree, the node number must increase by 2
         */
        //边界条件2:如果输入为1，那么结果就只有一个值为0的结点
        if(nodeCnt <=0 || (nodeCnt&1) == 0){
            return treeNodeList;
        }else if((nodeCnt|1) == 1){
            treeNodeList.add(new TreeNode(0));
            return treeNodeList;
        }
        //我们知道一共有N个结点，root占了1个结点，左子树可能有1，3，5，..，N-2个结点
        //对应的，右子树可能有N-2，..，5，3，1个结点
        //那么，我们可以用一个循环，找到所有可能的左右子树的可能的数量的情况，把root放进列表里
        for (int i = 1; i <= N-2; i += 2) {
            //这里就是递归的精髓了，每次看到递归，就一头雾水
            //在这里，我们不用去关心左右子树是怎么递归形成的
            //我们可以仅仅去关心，这个函数，它实现的是什么功能
            //allPossibleFBT(i)返回了一个列表，它存放着当结点数为i时，所有满足条件的树的root的集合
            //我们可以认为，allPossibleFBT(i)存放着所有满足条件的左子树的集合
            //同样，allPossibleFBT(N-1-i)存放着所有满足条件的右子树的集合
            //这是由static List<TreeNode> allPossibleFBT(int N)这个函数的定义所确定的
            List<TreeNode> leftSubTrees = allPossibleFBT(i);
            List<TreeNode> rightSubTrees = allPossibleFBT(N - i - 1);

            //接下来，就是左右子树的排列组合，当左子树为m时，右子树可能有right.size()个可能
            //所以一共有right.size() * left.size()种可能
            //我们把每一种排列，都放到我们所要的结果中
            for (TreeNode l : leftSubTrees) {
                for (TreeNode r : rightSubTrees) {
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    //对于左子树有i个结点，右子树有N-1-i个结点时，我们把所有可能的树add到列表里
                    treeNodeList.add(root);
                }
            }
        }
        return treeNodeList;
    }
}