## Wednesday, November 26, 2014

### [LeetCode] Unique Binary Search Trees I, II

Unique Binary Search Trees I

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```

Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
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
```
confused what `"{1,#,2,3}"` means? > read more on how binary tree is serialized on OJ.

n = 0

n = 1
1

n = 2
1                  2
\                /
2            1

n = 3
1           3    3      2     1
\        /     /       / \       \
3    2    1      1   3      2
/     /        \                    \
2   1          2                   3

f(0) = 1
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14``` ```class Solution { public: int numTrees(int n) { vector numBST(n+1,0); numBST[0] = 1; for(int i=1; i<=n; i++) { for(int j=0; j

1. 根节点可以任取min ~ max (例如min  = 1, max = n)，假如取定为i。
2. 则left subtree由min ~ i-1组成，假设可以有L种可能。right subtree由i+1 ~ max组成，假设有R种可能。生成所有可能的left/right subtree。
3 对于每个生成的left subtree/right subtree组合<T_left(p), T_right(q)>，p = 1...L，q = 1...R，添加上根节点i而组成一颗新树。

 ``` 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 26 27 28 29``` ```class Solution { public: vector generateTrees(int n) { return genBST(1, n); } vector genBST(int min, int max) { vector ret; if(min>max) { ret.push_back(NULL); return ret; } for(int i=min; i<=max; i++) { vector leftSubTree = genBST(min,i-1); vector rightSubTree = genBST(i+1,max); for(int j=0; jleft = leftSubTree[j]; root->right = rightSubTree[k]; ret.push_back(root); } } } return ret; } }; ```

#### 1 comment:

1. Thank you for sharing.