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.


思路: Unique Binary Search Trees I

首先注意这里是BST而不是普通的Binary Tree,所以数字会对插入的位置有影响。这类找combination/permutation的题都需要找找规律。

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(n)为unique BST的数量,以n = 3为例:

构造的BST的根节点可以取{1, 2, 3}中的任一数字。

如以1为节点,则left subtree只能有0个节点,而right subtree有2, 3两个节点。所以left/right subtree一共的combination数量为:f(0) * f(2) = 2

以2为节点,则left subtree只能为1,right subtree只能为2:f(1) * f(1) = 1

以3为节点,则left subtree有1, 2两个节点,right subtree有0个节点:f(2)*f(0) = 2

总结规律:
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<int> numBST(n+1,0);
        numBST[0] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=0; j<i; j++) {
                numBST[i] += numBST[j]*numBST[i-1-j];
            }
        }
        return numBST[n];
    }
};


思路: Unique Binary Search Trees II

要求生成所有的unique BST,类似combination/permutation的题目,可以递归构造。

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<TreeNode *> generateTrees(int n) {
        return genBST(1, n);
    }
    
    vector<TreeNode *> genBST(int min, int max) {
        vector<TreeNode *> ret;
        if(min>max) {
            ret.push_back(NULL);
            return ret;
        }
        
        for(int i=min; i<=max; i++) {
            vector<TreeNode*> leftSubTree = genBST(min,i-1);
            vector<TreeNode*> rightSubTree = genBST(i+1,max);
            for(int j=0; j<leftSubTree.size(); j++) {
                for(int k=0; k<rightSubTree.size(); k++) {
                    TreeNode *root = new TreeNode(i);
                    root->left = leftSubTree[j];
                    root->right = rightSubTree[k];
                    ret.push_back(root);
                }
            }
        }
        
        return ret;
    }
};

1 comment: