【题目】

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.

【分析】

参考：[LeetCode]96.Unique Binary Search Trees

【代码】

/*********************************
*   日期：2014-12-27
*   作者：SJF0115
*   题目: 95.Unique Binary Search Trees II
*   来源：https://oj.leetcode.com/problems/unique-binary-search-trees-ii/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        if (n <= 0){
            return generate(1, 0);
        }//if
        else{
            return generate(1, n);
        }
    }//
private:
    // 返回根节点结合
    vector<TreeNode*> generate(int start,int end){
        vector<TreeNode*> subTree;
        if(start > end){
            subTree.push_back(NULL);
            return subTree;
        }//if
        // i作为根节点
        for(int i = start;i <= end;i++){
            // 以i为根节点的树,其左子树由[start,i-1]构成,其右子树由[i+1,end]构成。
            // 返回的是不同二叉查找树的根节点，几种二叉查找树就返回几个根节点
            vector<TreeNode*> leftSubTree = generate(start,i-1);
            vector<TreeNode*> rightSubTree = generate(i+1,end);
            // 左子树右子树跟根节点连接
            // 以i为根的树的个数，等于左子树的个数乘以右子树的个数
            for(int j = 0;j < leftSubTree.size();j++){
                for(int k = 0;k < rightSubTree.size();k++){
                    TreeNode* node = new TreeNode(i);
                    node->left = leftSubTree[j];
                    node->right = rightSubTree[k];
                    subTree.push_back(node);
                }//for
            }//for
        }//for
        return subTree;
    }//
};
// 先序遍历
void PreOrder(TreeNode* root){
    if(root == NULL){
        return;
    }//if
    cout<<root->val<<" ";
    PreOrder(root->left);
    PreOrder(root->right);
}

int main() {
    Solution solution;
    vector<TreeNode*> vec = solution.generateTrees(3);
    for(int i = 0;i < vec.size();i++){
        TreeNode* root = vec[i];
        PreOrder(root);
        cout<<endl;
    }
}

[LeetCode]95.Unique Binary Search Trees II