leetcode - 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

分析及解答

 public int numTrees(int n) {//卡特兰数long result = 1;//防止在计算过程中，超出整数int的范围。for(int i = 0; i < n;i++){result = result * (2*n - i)/(i+1);//避免在除的过程因为有不能整除而造成的数的损失。(也避免long超出范围)}int r = Integer.parseInt(String.valueOf(result/(n+1)));//将long转为int.return r;}