1、



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

分析：本题非常easy想到用递归的方法，依次将每一个点作为根结点，然后递归左右子树，可是在这个递归中有个问题，怎样推断递归结束，怎样保留上层的结点，怎样推断递归的是左子树还是有子树，递归的写法还是非常重要的。本题中，採用每次先求得下层子树左右子树的结点，然后依据左右子树的不同情况形成不同的树，保存这些树的根结点。

代码例如以下：

class Solution {public:    vector
      
        generateTrees(int n) {        return constructTree(0,n-1);    }    vector
       
         constructTree(int startIndex, int endIndex){        vector
        
          result; //保存下一层的结点        if(startIndex > endIndex){            result.push_back(NULL);            return result;        }        for(int i=startIndex; i<=endIndex; ++i){            vector
         
           leftTrees = constructTree(startIndex,i-1);            vector
          
            rightTrees = constructTree(i+1,endIndex);            for(int j=0; j
           
            left = leftTrees[j]; newNode->right = rightTrees[k]; } } } return result; }};
           
          
         
        
       
      

2、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

分析：先做上面的题，后面这个题就简单了，採用递归，每次计算下层的左子树和右子树的数目，本层的不同树的个数为左子树的数目与右子树的数目相乘，每种不同的情况相加就可以。

class Solution {public:    int numTrees(int n) {        if(n < 1){            return 1;        }        return numTrees(1,n);    }    int numTrees(int startIndex, int endIndex){        int num = 1;        if(startIndex > endIndex){            return num;        }        num = 0;        for(int i=startIndex; i<=endIndex; ++i){            int leftNum = numTrees(startIndex,i-1);            int rightNum = numTrees(i+1,endIndex);            num += leftNum * rightNum;        }        return num;    }};