首页 > 代码库 > [LeetCode] Unique Binary Search Trees II (难以忍受的递归)

[LeetCode] 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

 

class Solution {private:    vector<TreeNode*> generateTreesRec(int start, int end){        vector<TreeNode*> v;        if(start > end){            v.push_back(NULL);            return v;        }        for(int i = start; i <= end; ++i){            vector<TreeNode*> left = generateTreesRec(start, i - 1);            vector<TreeNode*> right = generateTreesRec(i + 1, end);            TreeNode *node;            for(int j = 0; j < left.size(); ++j){                for(int k = 0; k < right.size(); ++k){                    node = new TreeNode(i);                    node->left = left[j];                    node->right = right[k];                    v.push_back(node);                }            }        }        return v;    }public:    vector<TreeNode *> generateTrees(int n) {        return generateTreesRec(1, n);    }};