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.

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPkhpZGUgVGFncyBUcmVlIER5bmFtaWMgUHJvZ3JhbW1pbmc8L3A+DQo8aHIgLz4NCjxwPtXitcDM4rK7ysfSu7XAtq/MrLnmu661xMzixL+jrLb4ysfSu7XAv8nS1Mq508O13bnpx/O94rXEzOLEv6GjPC9wPg0KPHA+1+6/qsq8v7S1vdXitcDM4s/rtb3Kx7fxv8nS1LC01dVVbmlxdWUgQmluYXJ5IFNlYXJjaCBUcmVlc9bQtcTLvMK3x/O94qOsvLS5zLao0ru49rj5vdq146Os09rKx7zZtqhuPTMsxMfDtMjnufvS1DHX986quPm92rXjo6zWu9Do0qrH83t91/fOqsv8tcTX89fTyvejrHsyLDN91/fOqsv8tcTT0tfTyvejrMi7uvPKudPDs8u3qNSt1PK+zb/J0tTH87P20tQxzqq4+b3ateO1xMv509DX08r3oaO1q8rHx/O94tfTyve1xM7KzOK6zdLUMc6quPm92rXjtcTL+dPQtv6y5svRy/fK97XEzsrM4rK7ysfNrNK7uPbOyszitvjT6zEmaGVsbGlwO27QzrPJtcTL+dPQtv6y5sr3ysfNrNK7uPbOyszioaM8YnIgLz4NCrj5vt3Jz8PmtcS31s7209rKx8/rtb3J6NLUaSZoZWxsaXA7Lmq1xNSqy9i5ubPJtcTL+dPQ19PK97XEuPm92rXjtcS8r7rPysdBW2ldW2pdo6zEx8O0v8nS1LHpwPppJmhlbGxpcDtq1tC1xMO/0ru49tSqy9hrLGkmbHQ7PWsmbHQ7PWqjrNSqy9hrtcTX89fTyvfKx2kuLmstMbm5s8m1xLb+subL0cv3yvfW0LXExLPSu8/uo6zUqsvYa7XE09LX08r3ysdrKzEmaGVsbGlwOy5qubmzybXEtv6y5svRy/fK99bQtcTEs9K7z+6jrM/W1NrV4rj219POyszivs26zdStyry1xM7KzOLKx82s0ru49s7KzOKjrL/J0tTKudPDtd256cfzveLBy6GjPGJyIC8+DQpydW50aW1lOjI0bXM8L3A+DQo8aHIgLz4NCjxwcmUgY2xhc3M9"brush:java;"> class Solution { public: vector generateTrees(int n) { vector result(1); if(n<=0) return result; return helper(1,n); } vector helper(int begin,int end) { vector result; if(begin==end) { result.push_back(new TreeNode(begin)); return result; } if(begin>end) return result; for(int i=begin;i<=end;i++) { vector leftRoot=helper(begin,i-1); vector rightRoot=helper(i+1,end); if(leftRoot.empty()) { for(int j=0;j left=NULL; base->right=rightRoot[j]; result.push_back(base); } } else if(rightRoot.empty()) { for(int j=0;j left=leftRoot[j]; base->right=NULL; result.push_back(base); } } else { for(int j=0;j left=leftRoot[j]; base->right=rightRoot[k]; result.push_back(base); } } } } return result; } }

然后看到了可以避免进行左右子树是否为空的判断的一个优化。这个优化的主要技巧是使用含有一个NULL元素的vector，这样就可以将左右子树为是否为空统一起来了。

/**
 * 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
   
     generateTrees(int n) { return helper(1,n); } vector
    
      helper(int begin,int end) { vector
     
       result; if(begin==end) { result.push_back(new TreeNode(begin)); return result; } if(begin>end) { result.push_back(NULL); return result; } for(int i=begin;i<=end;i++) { vector
      
        leftRoot=helper(begin,i-1); vector
       
         rightRoot=helper(i+1,end); for(int j=0;j
        
         left=leftRoot[j]; base->right=rightRoot[k]; result.push_back(base); } } } return result; } };