Lexi's Leetcode solutions

[leetcode] Unique Binary Search Trees | 给n,1~n的数字能组成多少种不同rotation的bst

Posted on: October 1, 2013

这题看似很难,因为树的rotation完全不会;但是咬牙想了五分钟就bug free的写出来了,一遍过,看来树的recursive理解已经挺到位了。

算法:1~n中每个数字都可以是root,定了谁是root之后(比如k),他的左子树只能是1~k-1组成的,右子树只能是k+1~n组成的。左子树的variation数目×右子树的就是k作为root的有几种rotation。有点要注意:终止条件有两种:

  1. p == q,说明就一个节点了,没啥可转的,就一种return 1
  2. 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;
}
Advertisements
Tags: , ,

1 Response to "[leetcode] Unique Binary Search Trees | 给n,1~n的数字能组成多少种不同rotation的bst"

高山仰止!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: