LeetCode894. All Possible Full B

1、题目链接

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

2、解题思路

这道题的意思是说，给你一个数N，表示一棵树的所有节点数，要求让你返回符合所有节点数是N的所有满二叉树的集合；可能听起来有点绕哈，听我慢慢道来，首先要理解一下满二叉树的概念，就是一棵树中，每一个节点的左右子节点都必须同时存在或者同时不存在；这是第一个条件，第二个条件是所有节点的数量加起来是N。一颗满二叉树，既然左右两个节点都存在，那么这棵树的节点数一定是基数，不要问我为什么，用心去感受>_<!!!，因为除了第一层根结点之外，每一层的节点数肯定是偶数，要不然就不符合满二叉树的条件，理解这一层概念之后，我们再来往下看，我们可以把这个问题缩小一下，分别求出以左节点和以右节点为根结点的两颗满二叉树，这样我们就把问题拆成了两个子问题，然后子问题又可以继续拆分，没错，有点动态规划的思想，但是我们的做法是用递归来完成：

3、代码

• Java

public List<TreeNode> allPossibleFBT(int N) {
    List<TreeNode> treeNodeList = new ArrayList<>();
    if (N == 1) {
        treeNodeList.add(new TreeNode(0));
    } else if (N % 2 == 1) {
        //奇数才有满二叉树
        TreeNode node;
        for (int i = 1; i < N; i += 2) {
            //递归左边节点的所有可能性
            for (TreeNode left : allPossibleFBT(i)) {
                //递归右边节点的所有可能性
                for (TreeNode right : allPossibleFBT(N - i - 1)) {
                    //将左右两边的节点合并
                    node = new TreeNode(0);
                    node.left = left;
                    node.right = right;
                    treeNodeList.add(node);
                }
            }
        }
    }
    return treeNodeList;
}

4、提交结果