96. Unique Binary Search Trees

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

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

96. Уникальные бинарные дерева поиска

Сколько существует различных по структуре бинарных деревьев поиска (БДП), состоящих из n вершин? Вершины пронумерованы числами 1...n.

Например, для n = 3 имеется 5 различных БДП.

1 3 3 2 1

\ / / / \ \

3 2 1 1 3 2

/ / \ \

2 1 2 3

class Solution {

public:

int numTrees(int n) {

}

};

РЕШЕНИЕ

числа Каталана

Анализ алгоритма

Количество искомых бинарных деревьев равно числам Каталана.

Корень бинарного дерева содержит одну вершину. Если левое поддерево содержит k вершин (0 £ k £ n – 1), то правое поддерево содержит (n – k – 1) вершину. Обозначим через f(n) количество бинарных деревьев с n вершинами. Тогда

f(n) = f(0) * f(n – 1) + f(1) * f(n – 2) + … + f(n – 1) * f(0),

то есть f(n) = c_n.

Реализация алгоритма

int cat[100];

class Solution

{

public:

int numTrees(int n)

{

cat[0] = cat[1] = 1;

for(int i = 2; i <= n; i++)

{

cat[i] = 0;

for(int j = 0; j < i; j++)

cat[i] = cat[i] + cat[j] * cat[i-j-1];

}

return cat[n];

}

};