2024.4.2每日一题

LeetCode

所有可能的真二叉树

题目链接：894. 所有可能的真二叉树 - 力扣（LeetCode）

题目描述

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

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

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

示例 1：

输入：n = 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]]

示例 2：

输入：n = 3
输出：[[0,0,0]]

提示：

• 1 <= n <= 20

思路

代码

C++

vector<TreeNode*> f[11];

auto init = [] {
    f[1] = {new TreeNode()};
    for (int i = 2; i < 11; i++) { // 计算 f[i]
        for (int j = 1; j < i; j++) { // 枚举左子树叶子数
            for (auto left : f[j]) { // 枚举左子树
                for (auto right : f[i - j]) { // 枚举右子树
                    f[i].push_back(new TreeNode(0, left, right));
                }
            }
        }
    }
    return 0;
}();

class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        return f[n % 2 ? (n + 1) / 2 : 0];
    }
};

Java

class Solution {
    private static final List<TreeNode>[] f = new ArrayList[11];

    static {
        Arrays.setAll(f, i -> new ArrayList<>());
        f[1].add(new TreeNode());
        for (int i = 2; i < f.length; i++) { // 计算 f[i]
            for (int j = 1; j < i; j++) { // 枚举左子树叶子数
                for (TreeNode left : f[j]) { // 枚举左子树
                    for (TreeNode right : f[i - j]) { // 枚举右子树
                        f[i].add(new TreeNode(0, left, right));
                    }
                }
            }
        }
    }

    public List<TreeNode> allPossibleFBT(int n) {
        return f[n % 2 > 0 ? (n + 1) / 2 : 0];
    }
}