Unique Binary Search Tree

96. Unique Binary Search Trees

题目描述

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

1
2
3
4
5
6
7
8
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

题目大意

给定一数字n,求有多少个BST组合。

解题思路

动态规划
如果n=1,ans=1。
如果n=2,ans=2。
如果n=3,ans=5。
如果n=4,ans=14。
可以发现规律:
f(0)=1
f(1)=f(0)
f(2)=f(0)f(1) + f(1)f(0)
f(3)=f(0)f(2) + f(1)f(1) + f(2)f(0)
f(4)=f(0)
f(3) + f(1)f(2) + f(2)f(1) + f(3)f(0)
.
.
.
f(n)=f(0)
f(n-1) + f(1)f(n-2) + …+f(n-1)f(0)

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
func numTrees(_ n: Int) -> Int {
var dp = Array(repeating: 0, count: n + 1)
dp[0] = 1
for i in 1...n {
for j in 0..<i {
dp[i] += dp[j] * dp[i - 1 - j]
}
}
return dp[n]
}
}

95. Unique Binary Search Trees II

题目描述

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

1
2
3
4
5
6
7
8
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

题目大意

给定一数字n,返回BST组合。跟I不同的是这里需要返回具体的BST。

解题思路

动态规划
使用递归生成左右节点,再将所有左右节点加在根节点。

代码

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
class Solution {
func generateTrees(_ n: Int) -> [TreeNode?] {
func recursion(min: Int, max: Int) -> [TreeNode?] {
var ans = [TreeNode?]()
guard min <= max else{ return [nil] }
for i in min...max {
let left = recursion(min: min, max: i - 1)
let right = recursion(min: i + 1, max: max)
for l in left {
for r in right {
let t = TreeNode(i)
t.left = l
t.right = r
ans.append(t)
}
}
}
return ans
}
guard n != 0 else{ return [] }
return recursion(min: 1, max: n)
}
}
0%