首页 > 代码库 > Unique Binary Search Trees

Unique Binary Search Trees

2024-07-18 02:28:47   228人阅读

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.

   1         3     3      2      1    \       /     /      / \           3     2     1      1   3      2    /     /       \                    2     1         2                 3

思路：若取第i个作为顶点，其对应二叉树个数为：numTrees(i-1)*numTrees(n-i)。加和所有不同i即可求解该题。此处，为了方便递归，令numTrees(0)取1。递归解法如下：

 1 class Solution { 2 public: 3     int numTrees( int n ) { 4         if( n == 0 ) { return 1; } 5         if( n <= 2 ) { return n; } 6         int num = 0; 7         for( int i = 1; i <= n/2; ++i ) { 8             num += 2 * numTrees( i-1 ) * numTrees( n-i ); 9         }10         if( n % 2 == 1 ) { num += numTrees( n/2 ) * numTrees( n/2 ); }11         return num;12     }13 };

使用num[i]保存numTrees(i)，动态规划解法如下：

 1 class Solution { 2 public: 3     int numTrees(int n) { 4         if( n <= 2 ) { return n; } 5         vector<int> num( n, 0 ); 6         num[0] = 1; num[1] = 2; 7         for( int i = 2; i < n; ++i ) { 8             num[i] += 2*num[i-1]; 9             for( int j = 1; j < i; ++j ) {10                 num[i] += num[j-1] * num[i-j-1];11             }12         }13         return num.back();14     }15 };

结果满足卡特兰递归式：h(n) = h(0)*h(n-1) + h(1)*h(n-2) + h(2)*h(n-3) + … + h(i)*h(n-i-1) + … + h(n-1)*h(0) ( n >= 2 )，且h(0) = 1，h(1) = 1。另一种递归形式为：h(n) = h(n-1) * (4*n-2) / (n+1)。

 1 class Solution { 2 public: 3     int numTrees( int n ) { 4         if( n <= 1 ) { return n; } 5         int catalan = 1; 6         for( int i = 2; i <= n; ++i ) { 7             catalan = catalan * (4*i-2) / (i+1); 8         } 9         return catalan;10     }11 };

 


联系
我们