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.
Hide Tags Tree Dynamic Programming
这道题不是一道动态规划的题目，而是一道可以使用递归求解的题目。
最开始看到这道题想到是否可以按照Unique Binary Search Trees中的思路求解，即固定一个根节点，于是假定n=3,那么如果以1作为根节点，只需要求{}作为它的左子树，{2,3}作为它的右子树，然后使用乘法原则就可以求出以1为根节点的所有子树。但是求解子树的问题和以1为根节点的所有二叉搜索树的问题不是同一个问题而与1…n形成的所有二叉树是同一个问题。 根据上面的分析于是想到设以i….j的元素构成的所有子树的根节点的集合是A[i][j]，那么可以遍历i…j中的每一个元素k,i<=k<=j，元素k的左子树是i..k-1构成的二叉搜索树中的某一项，元素k的右子树是k+1….j构成的二叉搜索树中的某一项，现在这个子问题就和原始的问题是同一个问题，可以使用递归求解了。 runtime:24ms
class Solution {public:vector<TreeNode*> generateTrees(int n) {vector<TreeNode *> result(1);if(n<=0)return result;return helper(1,n);}vector<TreeNode*> helper(int begin,int end){vector<TreeNode *> 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<TreeNode*> leftRoot=helper(begin,i-1);vector<TreeNode*> rightRoot=helper(i+1,end);if(leftRoot.empty()){for(int j=0;j<rightRoot.size();j++){TreeNode * base=new TreeNode(i);base->left=NULL;base->right=rightRoot[j];result.push_back(base);}}else if(rightRoot.empty()){for(int j=0;j<leftRoot.size();j++){TreeNode * base=new TreeNode(i);base->left=leftRoot[j];base->right=NULL;result.push_back(base);}}else{for(int j=0;j<leftRoot.size();j++){for(int k=0;k<rightRoot.size();k++){TreeNode * base=new TreeNode(i);base->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<TreeNode*> generateTrees(int n) {return helper(1,n);}vector<TreeNode*> helper(int begin,int end){vector<TreeNode *> 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<TreeNode*> leftRoot=helper(begin,i-1);vector<TreeNode*> rightRoot=helper(i+1,end);for(int j=0;j<leftRoot.size();j++){for(int k=0;k<rightRoot.size();k++){TreeNode * base=new TreeNode(i);base->left=leftRoot[j];base->right=rightRoot[k];result.push_back(base);}}}return result;}};
就得加倍付出汗水，赢得场场精彩
