leetcode oj java 96. Unique Binary Search Trees

本文主要是介绍leetcode oj java 96. 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.

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

二、解决方案：任何一个节点都可以做根节点，

num[0]=1;

num[1] = 1;

num[2] = num[0]*num[1] + num[1] + num[0] = 2;

num[n] = num[0]*num[n-1] + num[1] + num[n-2] + ...... + num[n-1]*num[0];

三、代码：

package T12;/*** @author 作者 : xcy* @version 创建时间：2016年12月30日 下午4:19:53*          类说明*/
public class t96 {public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println(numTrees(3));}public static int numTrees(int n) {int[] re = new int[n + 1];if (n == 0) {return 1;}if (n == 1) {return 1;}if (n == 2) {return 2;}re[0] = 1;re[1] = 1;re[2] = 2;for (int i = 3; i < n + 1; i++) {for (int j = 0; j < i; j++) {re[i] += re[j] * re[i - j - 1];}}return re[n];}}

这篇关于leetcode oj java 96. Unique Binary Search Trees的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---