【LeetCode-面试算法经典-Java实现】【096-Unique Binary Search Trees（唯一二叉搜索树）】
分类：LeetCode
【096-Unique Binary Search Trees（唯一二叉搜索树）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题
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.
13321\ /// \ \3211 32//\ \ 2123题目大意
给定一个n个结点的二叉搜索树，求一共有多少个不同类型的二叉搜索树。
解题思路
递推公式 f(k)*f(n-1-k)：f(k)表示根结点左子树有k个结点，其有的形状是f(k)，f(n-1-k)表示右子树有n-1-k个结点 f(n) = 2*f(n-1) + f(1)*f(n-2) + f(2)*f(n-3) + f(3)*f(n-4) + … +f(n-2)*f(1)
代码实现
算法实现类
public class Solution {(int n) {if (n <= 0) {return 0;} else if (n == 1) {return 1;}int[] result = new int[n + 1];result[0] = 0;result[1] = 1;// 求f(2)…f(n)for (int i = 2; i <= n; i++) {// 求f(i)result[i] = 2 * result[i – 1];for (int j = 1; j <= i – 1 ; j++) {result[i] += result[j]*result[i – 1 -j];}}return result[n];}}评测结果
点击图片，鼠标不释放，，拖动一段位置，释放后在新的窗口中查看完整图片。
特别说明欢迎转载，转载请注明出处【】
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇【LeetCode-面试算法经典-Java实现】【098-Validate Binary Search Tree（验证二叉搜索树）】下一篇【LeetCode-面试算法经典-Java实现】【100-Same Tree（两棵树是否相同）】
顶1踩0
即使爬到最高的山上，一次也只能脚踏实地地迈一步。
