95. Unique Binary Search Trees II
C++。思路如下：
- 对于连续整数序列
[left, right]中的一点i，若要生成以i为根节点的BST，则有如下规律：i左边的序列可以作为左子树结点，且左儿子可能有多个，所以有vector<TreeNode *> left_nodes = generate(left, i - 1);；i右边的序列可以作为右子树结点，同上所以有vector<TreeNode *> right_nodes = generate(i + 1, right);；- 产生的以当前
i为根结点的BST（子）树有left_nodes.size() * right_nodes.size()个，遍历每种情况，即可生成以i为根节点的BST序列； - 然后以
for循环使得[left, right]中每个结点都能生成子树序列。
即如下代码：
for (int i = left; i <= right; i++) { vector<TreeNode *> left_nodes = generate(left, i - 1); vector<TreeNode *> right_nodes = generate(i + 1, right); for (TreeNode *left_node : left_nodes) { for (TreeNode *right_node : right_nodes) { TreeNode *t = new TreeNode(i); t->left = left_node; t->right = right_node; ans.push_back(t); } } } -
一旦
left大于right，则说明这里无法产生子树，所以此处应该是作为空结点返回：ans.push_back(NULL); return ans;； - 返回
[left, right]中生成的所有子树序列ans。
代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
if (n) return generate(1, n);
else return vector<TreeNode *>{};
}
vector<TreeNode *> generate(int left, int right) {
vector<TreeNode *> ans;
if (left > right) {
ans.push_back(NULL);
return ans;
}
for (int i = left; i <= right; i++) {
vector<TreeNode *> left_nodes = generate(left, i - 1);
vector<TreeNode *> right_nodes = generate(i + 1, right);
for (TreeNode *left_node : left_nodes) {
for (TreeNode *right_node : right_nodes) {
TreeNode *t = new TreeNode(i);
t->left = left_node;
t->right = right_node;
ans.push_back(t);
}
}
}
return ans;
}
};
