LeetCode 96 - Unique Binary Search Trees

作者 QIFAN 日期 2017-01-06
LeetCode 96 - Unique Binary Search Trees

原题链接: 96. Unique Binary Search Trees


题干

给定 n ,求数字 1 ~ n 可以构成多少种不同的二叉树?

思路

首先想到几点

  • 二叉树的形态与插入顺序有很大的关系。
  • 第一个插入的数字对形态也有很大关系。

如果单纯考虑插入顺序,那一共有 $n!$ 种排法,显然二叉树的数量小于这个值。

来列举一下:

  • n = 1 ,只有 1 种
  • n = 2 ,有如下 2 种

    1 2
    \ /
    2 1
  • n = 3 ,有如下 5 种

    1 3 3 2 1
    \ / / / \ \
    3 2 1 1 3 2
    / / \ \
    2 1 2 3

这时候想到一点,如果将 i - 1 的看成一个树节点,那 i 的位置有 2 种情况:既可以作为该节点的父节点,也可以作为该节点的子节点。以 i = 3 为例,

1 3 1 2 3 2
\ ---> / \ / ---> / /\
2 1 2 1 2 1 3
\ \ /
2 3 1

这样就产生了 2 * 2 = 4 种情况。剩下一种应该怎么算?

1
\
3
/
2

这里 1 和 2 不再是整体,而分在了 3 的左右两边。
所以,若把 i - 1 个数分成两部分,使得 i 夹在中间,那这一共会有 dp[k] * dp[i - 1 - k] 种情况。

动态公式就出来了:
dp[i] = 2 \* dp[i - 1] + sum(dp[k] * dp[i - 1 - k]), 1 < k < i - 1

代码:

public int numTrees(int n) {
if (n <= 0) {
return 0;
}
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = 2 * dp[i - 1];
// 计算 i 插入前 i - 1 个数的情况
for (int k = 1; k < i - 1; k++) {
dp[i] += dp[k] * dp[i - 1 - k];
}
}
return dp[n];
}

此时时间复杂度为 $O(n^2)$ ,空间复杂度为 $O(n)$

Can we do better?

数学思路好像就是直接用 $C_{2n}^n / (n+1)$ ,这样就是 $O(n)$ 时间, $O(1)$ 空间。