生成所有不同的二叉搜索树

"二叉搜索树的不同构造方法" 在计算机科学中，二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，它的每个节点都包含一个键、一个关联的值、一个指向左子树的指针和一个指向右子树的指针。在二叉搜索树中，对于任何节点，其左子树中的所有节点的键都小于该节点的键，而右子树中所有节点的键都大于这个节点的键。这个问题涉及生成所有可能的不同的二叉搜索树，其中节点的值从1到n且互不相同。 题目要求我们根据给定的整数n，生成所有可能的二叉搜索树。由于树的结构是递归的，我们可以采用递归的方法来解决这个问题。参考答案提供的C++代码展示了如何实现这一过程。 ### 解决方案 首先，我们需要定义一个`TreeNode`类来表示树的节点，它通常包含三个属性：`val`（节点的值）、`left`（指向左子树的指针）和`right`（指向右子树的指针）。在C++中，这可以表示为： ```cpp struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; ``` 接下来，我们可以实现生成二叉搜索树的函数。这里有两个关键的递归步骤： 1. **基本情况**：当`start > end`时，表示没有节点可选，返回空指针`nullptr`，表示空树。 2. **递归情况**：对于每个`i`从`start`到`end`，我们可以选择`i`作为根节点。然后，分别对左子树和右子树进行递归调用，生成所有可能的左子树（`generateTrees(start, i - 1)`）和右子树（`generateTrees(i + 1, end)`）。接着，将所有左子树与所有右子树组合，构建新的二叉搜索树，并将其添加到结果集合`allTrees`中。 完整的`generateTrees`函数如下： ```cpp class Solution { public: vector<TreeNode*> generateTrees(int start, int end) { if (start > end) { return {nullptr}; } vector<TreeNode*> allTrees; for (int i = start; i <= end; i++) { vector<TreeNode*> leftTrees = generateTrees(start, i - 1); vector<TreeNode*> rightTrees = generateTrees(i + 1, end); for (auto& left : leftTrees) { for (auto& right : rightTrees) { TreeNode* currTree = new TreeNode(i); currTree->left = left; currTree->right = right; allTrees.emplace_back(currTree); } } } return allTrees; } vector<TreeNode*> generateTrees(int n) { if (!n) { return {}; } return generateTrees(1, n); } }; ``` 在上述代码中，`generateTrees`函数的主入口是`generateTrees(1, n)`，它初始化了从1到n的节点范围。然后，通过递归调用，我们可以生成所有可能的二叉搜索树，这些树的节点值从1到n且互不相同。 ### 示例 例如，当`n = 3`时，有5种不同的二叉搜索树： 1. 节点3作为根，节点1作为左子树，节点2作为右子树。 2. 节点3作为根，节点2作为左子树，节点1作为右子树。 3. 节点2作为根，节点1作为左子树，节点3作为右子树。 4. 节点1作为根，节点2作为右子树，节点3作为右子树的右子树。 5. 节点1作为根，节点3作为右子树，节点2作为右子树的左子树。 每个树的结构都满足二叉搜索树的特性，即左子树的所有节点小于根节点，右子树的所有节点大于根节点。 这个问题有助于理解二叉搜索树的性质以及递归在解决问题中的应用。在实际编程中，这种递归方法可用于生成各种数据结构，如树或图，只要它们的结构具有类似的递归性质。