简历:The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍:Introduction to Algorithms
编程珠玑:Programming Pearls (2nd Edition)
C++ 学习:The C++ Programming Language, 4th Edition
经典操作系统书籍,龙书:Operating System Concepts
创业:The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
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.
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
confused what
"{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
这道题我觉得很难,思路我有,就是左右子树递归填值,基本的idea 就是
node->val=i;
buildTree(node->left, l, i-1);
buildTree(node->right, i+1, r);
但问题是,我们要存的是一系列的子树,就是说一个n,它左右两边会有很多种类型的子树,它要全部都连接上,并且存到vector里面。这样逻辑就很难想明白(对于我这种recursion没有炉火纯青滴娃)。而且这里要用值传递,比较不浪费空间,不然都用指针,都在栈里面开辟空间,没调用一次都得开一堆东西,太麻烦。
我自己没想出来,参考了别人的答案。这个题可以让我们好好学习recursion。
后一个code用指针,因为涉及太多的vector数列,会需要用到很多拷贝构造,而且变量在栈上开辟。所以我们用指针来做。面试的时候注意。
后一个code用指针,因为涉及太多的vector数列,会需要用到很多拷贝构造,而且变量在栈上开辟。所以我们用指针来做。面试的时候注意。
No comments:
Post a Comment