不同的二叉搜索树I
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/*
思路：
设G(n) = f(1) + f(2) + ... + f(n)
其中f(n)表示i为根结点的搜索二叉树的数量
i
/ \
[1,,...,i-1] [i+1,i+2,...,n]
f(i) = G(i-1 - 1 + 1) * G(n - (i+1) + 1) = G(i-1) * G(n-i)
G(n) = G(0) * G(n-1) + G(1) * G(n-2) + ...+ G(n-1) * G(0)
*/
class Solution {
public:
int numTrees(int n) {
if (0 == n || 1 == n) return n;
int *dp = new int[n+1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = 0;
for (int j = 0; j < i; ++j) {
dp[i] += dp[j]*dp[i-1-j];
}
}
return dp[n];
}
};
不同的二叉搜索树II
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* 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) {
vector<TreeNode*> re;
if(n == 0) return re;
return build(1, n);
}
vector<TreeNode*> build(int start, int end) {
vector<TreeNode*> re;
if(start > end) {
re.push_back(nullptr);
return re;
}
for(int i = start; i <= end; ++i) {
vector<TreeNode *> left_v = build(start, i - 1);
vector<TreeNode *> right_v = build(i + 1, end);
for(auto left : left_v) {
for(auto right : right_v) {
TreeNode *root = new TreeNode(i);
root->left = left;
root->right = right;
re.push_back(root);
}
}
}
return re;
}
};
代码中的易错点（root指针初始化的位置）
vector<TreeNode*> build(int start, int end) {
vector<TreeNode*> re;
if(start > end) {
re.push_back(nullptr);
return re;
}
for(int i = start; i <= end; ++i) {
// 如果我们将root初始化在两层for循环的外面，这样进入vector的地址（root指针）是被拷贝进去了，不会变；
// 但是存在的问题就是root指针所指向的内容后面是不断的再被修改
// 因此我们的结果中会出现重复的内容，因为后面修改的把前面覆盖了
// 为了防止该情况我们只能每次在for循环最里面新new一个root指针，
// 保证每一个root指针都有一个属于自己的地址，各不相同，这样后面的修改就不会相互覆盖了
TreeNode *root = new TreeNode(i); // 错误写法
vector<TreeNode *> left_v = build(start, i - 1);
vector<TreeNode *> right_v = build(i + 1, end);
for(auto left : left_v) {
root->left = left;
for(auto right : right_v) {
root->right = right;
re.push_back(root);
}
}
}
return re;
}
