一级目录

二级目录

三级目录

力扣第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 作为子树。

---

2. 枚举每个节点作为根节点：

   for (int i = start; i <= end; i++) {
   

   • 遍历 [start, end] 范围内的每个数字，将其作为当前树的根节点。

---

3. 递归生成左右子树：

   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，递归生成其所有可能的左子树和右子树。

---

4. 组合左右子树：

   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 中。

---

5. 释放递归中动态分配的内存：

   free(leftTrees);
   free(rightTrees);
   

   • 左右子树数组在当前递归结束后不再需要，及时释放内存，避免内存泄漏。

---

6. 返回结果：

   *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=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$
     因此时间复杂度为 $O(C_n)$。
2. 空间复杂度：
   • 递归栈的深度为 $O(n)$。
   • 动态分配的内存和树的组合数量相关，为 $O(C_n)$。

---

输出示例

输入：

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 种不同的二叉搜索树的先序遍历结果。