自学内容网 自学内容网
自学内容网 > 正文

力扣第95题 不同的二叉搜索树 II

🕗 发布于 2024-12-09 20:27 leetcode  java  算法  

不同的二叉搜索树 II

一级目录

二级目录

三级目录

力扣第95题 - 不同的二叉搜索树 II

题目描述

给你一个整数 n，要求生成所有由 1 到 n 为节点所组成的 不同的二叉搜索树，并返回这些树的根节点。

思路分析

1. 二叉搜索树的性质
  • 左子树的所有节点值小于根节点值。
  • 右子树的所有节点值大于根节点值。
  • 以 1 到 n 的每个数字作为根节点时，左右子树的节点范围可以分别确定。
2. 递归构造树
  • 设 generateTrees(start, end) 表示生成从 start 到 end 的所有 BST：
    • 如果 start > end，返回 [NULL]（空树）。
    • 遍历 i 从 start 到 end，将 i 作为根节点：
      • 左子树：递归调用 generateTrees(start, i - 1)。
      • 右子树：递归调用 generateTrees(i + 1, end)。
    • 将所有可能的左子树和右子树组合，形成以 i 为根的所有树。
3. 动态规划优化（可选）
  • 利用备忘录保存 [start, end] 的计算结果，避免重复计算。

递归详细

递归函数定义

struct TreeNode** generateTreesHelper(int start, int end, int* returnSize)
参数含义
  1. start: 当前生成树的节点值范围的起始值。
  2. end: 当前生成树的节点值范围的结束值。
  3. returnSize: 用于返回生成的树的数量。
返回值

返回所有可能的 BST（以数组形式表示，数组中的每个元素是 BST 的根节点指针）。

递归的逻辑

  1. 递归结束条件（Base Case）：
    if (start > end) {
    *returnSize = 1;
    struct TreeNode** result = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    result[0] = NULL; // 空树
    return result;
}
    • 当 start > end 时，不存在可用节点，这表示一种有效的情况：返回空树。
    • 这种情况允许更高层的递归在左右子树组合时将 NULL 作为子树。
  1. 枚举每个节点作为根节点：
    for (int i = start; i <= end; i++) {
    • 遍历 [start, end] 范围内的每个数字，将其作为当前树的根节点。
  1. 递归生成左右子树：
    int leftSize = 0;
struct TreeNode** leftTrees = generateTreesHelper(start, i - 1, &leftSize);

int rightSize = 0;
struct TreeNode** rightTrees = generateTreesHelper(i + 1, end, &rightSize);
    • 左子树： 节点值范围为 [start, i-1]。
    • 右子树： 节点值范围为 [i+1, end]。
    • 对于每个可能的根节点 i，递归生成其所有可能的左子树和右子树。
  1. 组合左右子树：
    for (int l = 0; l < leftSize; l++) {
    for (int r = 0; r < rightSize; r++) {
        struct TreeNode* root = createNode(i);
        root->left = leftTrees[l];
        root->right = rightTrees[r];

        result = (struct TreeNode**)realloc(result, sizeof(struct TreeNode*) * (totalSize + 1));
        result[totalSize++] = root;
    }
}
    • 对于每个可能的左子树和右子树，组合成一棵以 i 为根的完整树：
      • leftTrees[l] 是某种可能的左子树。
      • rightTrees[r] 是某种可能的右子树。
    • 创建一个以 i 为值的新根节点 root。
    • 将 leftTrees[l] 连接到 root->left，将 rightTrees[r] 连接到 root->right。
    • 将组合完成的树加入结果数组 result 中。
  1. 释放递归中动态分配的内存：
    free(leftTrees);
free(rightTrees);
    • 左右子树数组在当前递归结束后不再需要，及时释放内存，避免内存泄漏。
  1. 返回结果：
    *returnSize = totalSize;
return result;
    • 将生成的树的数量保存在 returnSize 中。
    • 返回所有可能的 BST。

递归过程的可视化

以 n = 3 为例，调用 generateTrees(3, &returnSize)：

第一次递归（范围 [1, 3]）
  • 枚举根节点：1, 2, 3。
  • 例如，当根节点为 2：
    • 左子树范围： [1, 1]
    • 右子树范围： [3, 3]
第二次递归（范围 [1, 1] 和 [3, 3]）
  • 对于左子树 [1, 1]：
    • 唯一根节点为 1，左右子树均为空。
  • 对于右子树 [3, 3]：
    • 唯一根节点为 3，左右子树均为空。
第三次递归组合（根节点 2）
  • 左子树为 [1]。
  • 右子树为 [3]。
  • 组合成以 2 为根的树：
        2
   / \
  1   3
递归退出条件
  • 当范围无效（如 [4, 3]），返回空树 [NULL]。

完整流程

递归通过分解问题，将大范围 [1, n] 的树拆分成多个小范围 [start, end] 的子树，最终组合成所有可能的二叉搜索树。

递归优势

  • 分治思想： 将问题拆解为左右子树独立生成的子问题，最后组合。
  • 灵活性： 能动态处理不同的 n，适用于范围大小不定的树生成问题。
  • 简洁性： 通过递归和迭代组合，代码结构清晰易读。

算法实现

C语言实现
#include <stdio.h>
#include <stdlib.h>

// 定义树的结构
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 创建一个新节点
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 生成从 start 到 end 的所有 BST
struct TreeNode** generateTreesHelper(int start, int end, int* returnSize) {
    if (start > end) {
        *returnSize = 1;
        struct TreeNode** result = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        result[0] = NULL;
        return result;
    }

    int totalSize = 0;
    struct TreeNode** result = NULL;

    for (int i = start; i <= end; i++) {
        // 左子树
        int leftSize = 0;
        struct TreeNode** leftTrees = generateTreesHelper(start, i - 1, &leftSize);

        // 右子树
        int rightSize = 0;
        struct TreeNode** rightTrees = generateTreesHelper(i + 1, end, &rightSize);

        // 组合左右子树和当前根节点
        for (int l = 0; l < leftSize; l++) {
            for (int r = 0; r < rightSize; r++) {
                struct TreeNode* root = createNode(i);
                root->left = leftTrees[l];
                root->right = rightTrees[r];

                result = (struct TreeNode**)realloc(result, sizeof(struct TreeNode*) * (totalSize + 1));
                result[totalSize++] = root;
            }
        }

        free(leftTrees);
        free(rightTrees);
    }

    *returnSize = totalSize;
    return result;
}

// 主函数：生成从 1 到 n 的所有 BST
struct TreeNode** generateTrees(int n, int* returnSize) {
    if (n == 0) {
        *returnSize = 0;
        return NULL;
    }
    return generateTreesHelper(1, n, returnSize);
}

// 测试用例打印树（先序遍历）
void printTree(struct TreeNode* root) {
    if (!root) {
        printf("null ");
        return;
    }
    printf("%d ", root->val);
    printTree(root->left);
    printTree(root->right);
}

int main() {
    int returnSize;
    struct TreeNode** trees = generateTrees(3, &returnSize);

    printf("Generated %d unique BSTs:\n", returnSize);
    for (int i = 0; i < returnSize; i++) {
        printTree(trees[i]);
        printf("\n");
    }

    return 0;
}

关键点解析

  1. 递归终止条件：当 start > end 时返回空树 [NULL]。
  2. 组合左右子树：
    • 遍历 start 到 end，每个数都可能是根节点。
    • 对每个根节点，递归生成左右子树并组合。
  3. 内存管理：
    • 动态分配数组用于保存不同的树。
    • 组合树时需考虑 realloc 的正确使用。

复杂度分析

  1. 时间复杂度：
    • 递归中，每次会分成多个子问题，时间复杂度近似为生成不同 BST 的卡特兰数 C n C_n Cn​：
      C n = 1 n + 1 ( 2 n n ) C_n = \frac{1}{n+1} \binom{2n}{n} Cn​=n+11​(n2n​)
      因此时间复杂度为 O ( C n ) O(C_n) O(Cn​)。
  2. 空间复杂度：
    • 递归栈的深度为 O ( n ) O(n) O(n)。
    • 动态分配的内存和树的组合数量相关，为 O ( C n ) O(C_n) O(Cn​)。

输出示例

输入：
n = 3
输出：
Generated 5 unique BSTs:
1 null 2 null 3
1 null 3 2 null
2 1 null 3 null
3 1 null null 2
3 2 null null 1

这表示 5 种不同的二叉搜索树的先序遍历结果。


原文地址：https://blog.csdn.net/weixin_48941116/article/details/144329363

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024