LC95 Unique Binary Search Tree

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]

/**
 * Definition for a binary tree node.
 * 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 < 1)
            return vector<TreeNode*>(0);
        return genRoots(1, n);
    }
    vector<TreeNode*> genRoots(int start, int end){
        vector<TreeNode*> res;
        if(start > end){
            return vector<TreeNode*>(1,NULL);
        }

        for(int i = start; i <= end; i ++){
            vector<TreeNode*>left = genRoots(start, i - 1);
            vector<TreeNode*>right = genRoots(i + 1, end);    
            //then put the connect the root with all possible left and right child
            for(int j = 0; j < left.size(); j ++){
                for(int k = 0; k < right.size(); k ++){
                    TreeNode *curRoot = new TreeNode(i);
                    curRoot -> left = left[j];
                    curRoot -> right = right[k];
                    res.push_back(curRoot);
                }
            }
        }
    return res;   
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax