96.不同的二叉搜索树
Snake8859 二叉树
# 题目描述
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3
输出:5
1
2
2
示例 2:
输入:n = 1
输出:1
1
2
2
# 外地解法-二叉搜索树的构造
二叉树算法的关键就在于明确根节点需要做什么,其实 BST 作为一种特殊的二叉树,核心思路也是一样的。
举个例子,比如给算法输入n = 5
,也就是说用{1,2,3,4,5}
这些数字去构造 BST。
首先,这棵 BST 的根节点总共有几种情况?显然有 5 种情况对吧,因为每个数字都可以作为根节点。比如说我们固定3
作为根节点,这个前提下能有几种不同的 BST 呢?根据 BST 的特性,根节点的左子树都比根节点的值小,右子树的值都比根节点的值大。所以如果固定3
作为根节点,左子树节点就是{1,2}
的组合,右子树就是{4,5}
的组合。
左子树的组合数和右子树的组合数乘积就是3
作为根节点时的 BST 个数。
我们这是说了3
为根节点这一种特殊情况,其实其他的节点也是一样的。
那你可能会问,我们可以一眼看出{1,2}
和{4,5}
有几种组合,但是怎么让算法进行计算呢?
其实很简单,只需要递归就行了,我们可以写这样一个函数:
// 定义:闭区间 [lo, hi] 的数字能组成 count(lo, hi) 种 BST
int count(int lo, int hi);
1
2
2
根据这个函数的定义,结合刚才的分析,可以写出代码:
/* 主函数 */
int numTrees(int n) {
// 计算闭区间 [1, n] 组成的 BST 个数
return count(1, n);
}
/* 计算闭区间 [lo, hi] 组成的 BST 个数 */
int count(int lo, int hi) {
// base case
if (lo > hi) return 1;
int res = 0;
for (int i = lo; i <= hi; i++) {
// i 的值作为根节点 root
int left = count(lo, i - 1);
int right = count(i + 1, hi);
// 左右子树的组合数乘积是 BST 的总数
res += left * right;
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
注意 base case,显然当lo > hi
闭区间[lo, hi]
肯定是个空区间,也就对应着空节点 null,虽然是空节点,但是也是一种情况,所以要返回 1 而不能返回 0。
这样,题目的要求已经实现了,但是时间复杂度非常高,肯定存在重叠子问题。
前文动态规划相关的问题多次讲过消除重叠子问题的方法,无非就是加一个备忘录:
class Solution {
int[][] memo; // 备忘录
public int numTrees(int n) {
// 备忘录初始化,值为0
memo = new int[n+1][n+1];
// 计算闭区间[1...n]组成的BST个数
return count(1, n);
}
// 计算闭区间[lo...hi]组成的BST个数
public int count(int lo, int hi){
if(lo > hi) return 1;
if(memo[lo][hi] != 0) return memo[lo][hi];
int res = 0;
for(int i = lo; i <= hi; i++){
// 以i作为根节点root
int left = count(lo, i - 1);
int right = count(i + 1, hi);
// 左右子树的组合乘积就是BST的总数
res += left * right;
}
memo[lo][hi] = res;
return memo[lo][hi];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32