[leetcode] Unique Binary Search Trees | 给n,1~n的数字能组成多少种不同rotation的bst
Posted October 1, 2013
on:这题看似很难,因为树的rotation完全不会;但是咬牙想了五分钟就bug free的写出来了,一遍过,看来树的recursive理解已经挺到位了。
算法:1~n中每个数字都可以是root,定了谁是root之后(比如k),他的左子树只能是1~k-1组成的,右子树只能是k+1~n组成的。左子树的variation数目×右子树的就是k作为root的有几种rotation。有点要注意:终止条件有两种:
- p == q,说明就一个节点了,没啥可转的,就一种return 1
- p > q,说明这一段已经不存在了,这时不应该return 0,因为这正是子树是null的情况!所以还应该return 1
public int numTrees(int n) { return getWays(1, n); } int getWays(int p, int q) { if (p >= q) return 1; int ways = 0; for (int i = p; i <= q; i++) { int leftWays = getWays(p, i - 1); int rightWays = getWays(i + 1, q); ways += leftWays * rightWays; } return ways; }
April 6, 2014 at 11:00 am
高山仰止!