95. Unique Binary Search Trees II
发布时间:2020-12-14 04:48:19 所属栏目:大数据 来源:网络整理
导读:问题描述: Given an integer? n ,generate all structurally unique?BST‘s?(binary search trees) that store values 1 ...? n . Example: Input: 3Output:[? [1,null,3,2],? [3,2,1],1,? [2,3],? [1,3]]Explanation:The above output corresponds to the
问题描述: 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,1],1,? [2,3],? [1,3] ] Explanation: The above output corresponds to the 5 unique BST‘s shown below: 1 3 3 2 1 / / / 3 2 1 1 3 2 / / 2 1 2 3 ? 解题思路: 这道题可以用dfs做,可是我再写辅助方法的时候,遇到了一个问题:到底该返回什么? 如果我返回的是TreeNode*那我们什么时候将树压入返回数组中? 用dfs时调用递归,如果在递归的最底层压入,实际上压入的是一个单个的node!因为左子树和右子树还在等你赋值! 所以这里返回vector<TreeNode*>。 在一个区间内所有的树的可能性。 但是我的运行效率非常低:28ms:打败了7.67%... 大神也考虑到了这点,并且用了指针来改进,我一会研究! 还有DP解法的。 代码: /** * 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) { vector<TreeNode*> ret; if(n == 0) return ret; return constructTree(1,n); } private: vector<TreeNode*> constructTree(int start,int end){ vector<TreeNode*> subTree; if(start > end) subTree.push_back(NULL); else{ for(int i = start; i <= end; i++){ vector<TreeNode*> leftSub = constructTree(start,i-1); vector<TreeNode*> rightSub = constructTree(i+1,end); for(int a = 0; a < leftSub.size(); a++){ for(int b = 0; b < rightSub.size(); b++){ TreeNode* root = new TreeNode(i); root->left = leftSub[a]; root->right = rightSub[b]; subTree.push_back(root); } } } } return subTree; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |