Thursday, July 18, 2013

Unique Binary Tree II@leetcode

刷题必备书籍Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历: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.
   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数列,会需要用到很多拷贝构造,而且变量在栈上开辟。所以我们用指针来做。面试的时候注意。


No comments:

Post a Comment

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...