C3eaca7912fcc19c36a8bfbc0fd33983
(难度Medium)Problem 96. Unique Binary Search Trees(唯一的生成树个数)

链接

Unique Binary Search Trees - LeetCode

难度等级

Medium

题干

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

题意

和上题比较近似,给定一个整数n,需要用1-n这n个整数生成二叉搜索树。但是这题求的不是所有搜索树,而是不同的搜索树的棵数。

样例

Example:

Input: 3
Output: 5
Explanation:
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

题解

很明显,这题是上一题的简化版,我们当然可以复用上一题的代码,最后计算一下vector当中的数量。但是,实际上是没有必要的,因为我们没必要真的把每一棵树都建出来,这非常浪费时间。

聪明的同学不能想出来,当我们把根节点设置成i,那么1-i就是它的左子树,i+1-n就是它的右子树。那么以i节点为根节点的总数就等于dfs(1, i-1) * dfs(i+1, n)

显然,当n=1或者0的时候,答案是1.

到这里为止,代码已经呼之欲出了。

```
class Solution {
public:

int dfs(int n) {
    if (n <= 1) {
top Created with Sketch.