96. Unique Binary Search Trees
题目描述
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
|
|
题目大意
给定一数字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)
代码
|
|
95. Unique Binary Search Trees II
题目描述
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
|
|
题目大意
给定一数字n,返回BST组合。跟I不同的是这里需要返回具体的BST。
解题思路
动态规划
使用递归生成左右节点,再将所有左右节点加在根节点。
代码
|
|