二叉查找树在数据结构中学习，但是感觉自己学的非常水，最近在lintCode上做了两道的关于二叉查找树的题，感觉有比较记录下来，就当是增强记忆！
1.二叉查找树I
题意：
给出 n，问由 1...n 为节点组成的不同的二叉查找树有多少种？
样例：
给出n = 3，生成所有5种不同形态的二叉查找树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
这个是数据结构中的二叉树中非常的常见。这个是典型卡特兰数的样例
(1).卡特兰数
令h(0)=1，h(1)=1，卡特兰数满足递归式：h(n) = h(0)h(n-1) + h(1)h(n-2) + ... + h(n-1)*h(0) (n>=2)；该递推公式为：h(n) = C(2n,n)/(n+1)，n=0,1,2,3,...
(2).为什么二叉查找树满足卡特兰数呢？
我们这样来假设
当只有一个节点时，肯定只有一种情况，我们于是假设f(1) = 1;
当只有两个节点时，怎么来考虑？我们固定一个节点，另一个节点要么放在左子树，要么放在右子树，所以分为两种情况，f(2) = f(1) + f(1)。其中的f(1),我们这样来理解，第一个f(1)实际上是f(1) * f(0)(这里的f(0)等于1，为什么f(0)等于1呢？因为没有节点也只有一种情况啊！),表示意思是，左子树只有一个节点，右子树没有节点，而第二个f(1)表示为f(0) * f(1)，表示的是左子树没有节点，右子树只有一个节点。
当只有三个或者三个节点以上时，我们假设为n， f(n)的情况就分为左子树为0并且右子树为n - 1(因为有一个节点被固定了，所以只有n - 1个节点)，左子树为1并且右子树为n - 2，左子树为2并且右子树为 n - 3等等...然后我们就可以退出公式：f(n) = f(0) * f(n - 1) + f(1) * f(n - 2) + ...... + f(n - 2) * f(1) + f(n - 1) * f(1)。
(3).动态规划
根据上面的递归公式，我们可以写出动态规划的代码
public int numTrees(int n) {
int nums[] = new int[n + 1];
nums[0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < i; j++) {
nums[i] += nums[j] * nums[i - 1- j];
}
}
return nums[n];
}
2.二叉查找树II
题意：
给出n，生成所有由1...n为节点组成的不同的二叉查找树
样例：
给出n = 3，生成所有5种不同形态的二叉查找树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
说实话，这道题真的不知道怎么写，标签上写的是深搜，但是就是不知道怎么写出来，因为之前只写过深搜的搜索题，没有做过深搜的生成类型题！
最后我在网络上找的别人的代码，然后理解了，也不知道理解的是否正确。
先来看看代码
public List<TreeNode> generateTrees(int n) {
List<TreeNode> list = new ArrayList<>();
if(n < 0) {
return null;
}
list = createTree(1, n);
return list;
}
private List<TreeNode> createTree(int start, int end) {
List<TreeNode> list = new ArrayList<>();
if (start > end) {
list.add(null);
return list;
}
for (int i = start; i <= end; i++) {
List<TreeNode> left = createTree(start, i - 1);
List<TreeNode> right = createTree(i + 1, end);
for (int j = 0; j < left.size(); j++) {
for (int k = 0; k < right.size(); k++) {
TreeNode node = new TreeNode(i);
node.left = left.get(j);
node.right = right.get(k);
list.add(node);
}
}
}
return list;
}
我是这样理解的：比如n个节点，它有分为n - 1种情况，跟上面的卡特兰数一样，然后我们分别构造当前节点的左子树和右子树，通过递归来构造。由于有n - 1种情况，所以得有一个循环来构造。
网友评论