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

Posted by: lexigrey on: October 1, 2013

• In: leetcode
• 1 Comment

这题看似很难，因为树的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;
}

Tags: BST, tree, 后序