首页 > 代码库 > Leetcode-Unique Binary Search Trees

Leetcode-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
Have you met this question in a real interview?
 
Solution:
 1 public class Solution { 2     public int numTrees(int n) { 3         int[] d = new int[n+1]; 4         Arrays.fill(d,0); 5         d[0] = 1; 6         for (int i=1;i<=n;i++) 7             for (int j=1;j<=i;j++) 8                 d[i] += d[j-1]*d[i-j]; 9         return d[n];10     }11 }

 

Leetcode-Unique Binary Search Trees