TNotes.leetcode

Appearance

⏰0894. 所有可能的真二叉树【中等】

0894. 所有可能的真二叉树【中等】 ​

1. 📝 题目描述 ​

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

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

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

示例 1：

img

txt
输入：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：

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

提示：

  • 1 <= n <= 20

2. 🎯 s.1 - 递归 ​

c
struct TreeNode** allPossibleFBT(int n, int* returnSize) {
    if (n % 2 == 0) { *returnSize = 0; return NULL; }
    if (n == 1) {
        struct TreeNode** res = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        res[0] = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
        *returnSize = 1;
        return res;
    }
    int cap = 100;
    struct TreeNode** res = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * cap);
    *returnSize = 0;
    for (int i = 1; i < n; i += 2) {
        int lSize, rSize;
        struct TreeNode** lefts = allPossibleFBT(i, &lSize);
        struct TreeNode** rights = allPossibleFBT(n - 1 - i, &rSize);
        for (int a = 0; a < lSize; a++) {
            for (int b = 0; b < rSize; b++) {
                if (*returnSize == cap) { cap *= 2; res = realloc(res, sizeof(struct TreeNode*) * cap); }
                struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                node->val = 0; node->left = lefts[a]; node->right = rights[b];
                res[(*returnSize)++] = node;
            }
        }
        free(lefts); free(rights);
    }
    return res;
}
js
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var allPossibleFBT = function (n) {
  if (n % 2 === 0) return []
  if (n === 1) return [new TreeNode(0)]
  const res = []
  for (let i = 1; i < n; i += 2) {
    const lefts = allPossibleFBT(i)
    const rights = allPossibleFBT(n - 1 - i)
    for (const l of lefts)
      for (const r of rights) res.push(new TreeNode(0, l, r))
  }
  return res
}
py
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n % 2 == 0: return []
        if n == 1: return [TreeNode(0)]
        res = []
        for i in range(1, n, 2):
            for l in self.allPossibleFBT(i):
                for r in self.allPossibleFBT(n - 1 - i):
                    res.append(TreeNode(0, l, r))
        return res
  • 时间复杂度：O(2n/2)，即第 n/2 个卡特兰数
  • 空间复杂度：O(2n/2)

算法思路：

  • 真二叉树节点数必为奇数，枚举左子树节点数 i（奇数）
  • 递归生成所有左子树和右子树的组合