leetcode 894. 所有可能的满二叉树

满二叉树是一类二叉树,其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

 

示例:

输入:7
输出:[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
解释:

 leetcode 894. 所有可能的满二叉树

提示:

1 <= N <= 20

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/all-possible-full-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

dp数组记录从1-n个节点所构成的二叉树

1:创建一个长度为你+ 1的list的数组, 其每一项代表 i 个数所构成的树。

2:当计算 i 个节点构成的二叉树的个数的时候,

其左节点的个数分别为 (1, 3, 5, 7...i - 2)

其右节点的对应的个数分别为 (i - 2, i - 4, i - 6, i - 8...1)

所以从数组中取出对应的list集合,组合构建即可。

/**
 * 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 {
    public List<TreeNode> allPossibleFBT(int n) {
        if ((n & 1) == 0) {
            return Collections.emptyList();
        }
        List[] arr = new ArrayList[n + 1];
        arr[1] = new ArrayList<>(1);
        arr[1].add(new TreeNode(0));
        for (int i = 3; i <= n; i = i + 2) {
            List<TreeNode> list = new ArrayList<>();
            arr[i] = list;
            for (int j = 1; j < i; j = j + 2) {
                for (TreeNode right : (List<TreeNode>) arr[i - j - 1]) {
                    for (TreeNode left : (List<TreeNode>) arr[j]) {
                        TreeNode node = new TreeNode(0);
                        node.right = right;
                        node.left = left;
                        list.add(node);
                    }
                }
            }
        }
        return arr[n];
    }
}

leetcode 894. 所有可能的满二叉树

leetcode 894. 所有可能的满二叉树

上一篇:Restful风格编码


下一篇:网络信息安全技术实验3