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] ] 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
Constraints:
0 <= n <= 8
A:
难点就在于,左边和右边的子树是相乘关系,而非相加。
所以,我们这里用了循环,每次create一个新的树(为节省空间,在两个for loop迭代的时候, 新树只有root才是新的,别的都是指向旧的指针)。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<TreeNode*> generateTrees(int n) { if(n==0) return vector<TreeNode*>(); return helper(1,n); } private: vector<TreeNode*> helper(int a, int b){ vector<TreeNode*> res; if(a>b){ res.push_back(nullptr); } for(int i = a; i<=b;i++){ auto vL = helper(a,i-1); auto vR = helper(i+1,b); for(auto ll : vL){ for(auto rr : vR){ TreeNode * root = new TreeNode(i, ll, rr); res.push_back(root); } } } return res; } };
Mistakes:
1: 当左边或者右边的子树为空的时候,单纯利用两个for循环是不对的,因为这时候,可以把另一半直接加上就是了。
这时候,要先判断 size() 是否为0 ----------- 代码见那几个for循环。
2: 当 input 为0,( 这个,就是题意没讲清楚了)。
Input: | 0 | ||
Output: | [] | ||
Expected: | [{}] |
原因是--------- 前面有个return
Learned:
TreeNode * root = new TreeNode(i, ll, rr); res.push_back(root);
这几句一开始是这样写的:
TreeNode root(i, ll, rr);
res.push_back(&root); 可是这样不对, 不知道为什么
错误提示为:
ERROR: AddressSanitizer: stack-use-after-scope on address 0x7ffe12385e00 at pc 0x00000042003f bp 0x7ffe12384f80 sp 0x7ffe12384f78
READ of size 4 at 0x7ffe12385e00 thread T0
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
(longjmp and C++ exceptions are supported)
(longjmp and C++ exceptions are supported)
1: 还是要动手写, 光自己在那里,玩儿着想,想不深。 也难以持续。
2: 因为自己本来的代码里面,存在大量的对象数据的拷贝。 其实,是可以仅仅用指针来解决的(虽然这道题目里面,也没有多用多少空间。但当对象大了之后, 还是很显著的)
所以,我原本的代码
远不如现在的代码;
2: 因为自己本来的代码里面,存在大量的对象数据的拷贝。 其实,是可以仅仅用指针来解决的(虽然这道题目里面,也没有多用多少空间。但当对象大了之后, 还是很显著的)
所以,我原本的代码
for (int i = 0; i < alLeft.size(); i++) { for (int j = 0; j < alRight.size(); j++) { // create a new node, and copy left to right TreeNode tmpTree = createNewTree(rootValue, alLeft.get(i), alRight.get(j)); all.add(tmpTree);// add the values rooted at rootValue, // with one variation of left and // right child } // end of loop for each of the right side subtree } // end of for loop for each of Left side subtree
远不如现在的代码;
No comments:
Post a Comment