Unique Binary Search Trees

发表于   |   分类于 ， ，

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example
Given n = 3, there are a total of 5 unique BST’s.

描述

给出一个 n，能组成多少种不同的二叉搜索树

分析

假设有 n 个节点，任选其中的一个节点为根，所可行的二叉搜索树的数量等于左右子树二叉搜索树数量的乘积

例如：

  • n = 0 , h(0) = 1
  • n = 1 , h(1) = 1
  • n = 2 , h(2) = h(0)h(1) + h(1)h(0) , 即取一个节点为根节点后，左子树为空，右子树一个节点，或者左子树一个节点，右子树为空

观察可得，这是卡特兰数的特征，由此可以推出以下解法：

代码

$h(0)=1 \; , \; h(1)=1$
$h(n)=h(0)h(n-1)+h(1)h(n-2)+ \cdots +h(n-1)h(0)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int numTrees(int n) {

        int[] catalan = new int[n + 1];
        java.util.Arrays.fill(catalan, 0);
        catalan[0] = catalan[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                catalan[i] += (catalan[j] * catalan[i - j - 1]);
            }
        }

        return catalan[n];
    }
}

$h(1)=1$
$h(n)=h(n-1)(4n-2)/(n+1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int numTrees(int n) {

        double catalan = 1.0;

        for (int i = 2; i <= n; i++) {
            catalan = catalan * ((4 * i - 2) * 1.0 / (i + 1));
        }

        return (int) catalan;

    }
}