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%