Keshawn_lu's Blog

Leetcode 96. 不同的二叉搜索树

字数统计: 362阅读时长: 1 min
2020/07/15 Share

题目简介:

给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

示例:

1
2
3
4
5
6
7
8
9
10
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

思路:

动态规划,dp[i]代表i个节点能构成的二叉搜索树数量。

首先若有i个节点,那么节点1,2,3,...,i都能作为根节点。

我们假设以3作为根节点,那么左子树为1,2,右子树为4,5,6,...,i

所以左子树构成二叉搜索树的数量为dp[2],右子树构成二叉搜索树的数量为dp[i - 3](有i - 3个节点)。

所以i个节点,并以3作为根节点所能构成的二叉搜索树总数为dp[2] * dp[i - 3]

所以我们只要循环节点1 ... i,把每个节点当做根节点时能构成的二叉搜索树数量累加即可,答案即为dp[i]

tips:

  • dp[0]代表空树的情况,dp[0] = 1
  • dp[1]代表只有一个节点的情况,dp[1] = 1

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int numTrees(int n) {

vector<int> dp(n + 1, 0);

dp[0] = 1; //空树
dp[1] = 1; //一个结点

for(int i = 2; i < n + 1; i++){

for(int j = 1; j <= i; j++){

dp[i] += dp[j - 1] * dp[i - j];
}
}

return dp[n];
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: