感恩发面经-Amazon第二轮电面 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

感恩发面经-Amazon第二轮电面

感恩发面经-Amazon第二轮电面# JobHunting - 待字闺中

w*h2011-11-24 08:11

1 楼

白
谈research;
什么是binary search tree?
如何validate a BST? 写code，给了递归解法；
follow-up, 如何用非递归方法解决这个问题，coding;
问问题。

n*w2011-11-24 08:11

2 楼

A也开始问非递归解法了。

q*x2011-11-24 08:11

3 楼

非递归解法是啥？用栈实现中序周游？

【在 w**h 的大作中提到】

: 白
: 谈research;
: 什么是binary search tree?
: 如何validate a BST? 写code，给了递归解法；
: follow-up, 如何用非递归方法解决这个问题，coding;
: 问问题。

A*u2011-11-24 08:11

4 楼

你运气太好了。。。
cong
第三题目这里有方法， method 4 in order
http://www.geeksforgeeks.org/archives/3042
http://www.leetcode.com/2010/04/binary-search-tree-in-order-tra

【在 w**h 的大作中提到】

: 白
: 谈research;
: 什么是binary search tree?
: 如何validate a BST? 写code，给了递归解法；
: follow-up, 如何用非递归方法解决这个问题，coding;
: 问问题。

s*n2011-11-24 08:11

5 楼

第3题就是写个Tree的中序遍历吧？

n*w2011-11-24 08:11

6 楼

非递归的话，中序比较好写，但是并不graceful。
另外可以设计个数据结构，用先序后序遍历也行。

s*n2011-11-24 08:11

7 楼

展开说说用先序？

【在 n*******w 的大作中提到】

: 非递归的话，中序比较好写，但是并不graceful。
: 另外可以设计个数据结构，用先序后序遍历也行。

s*n2011-11-24 08:11

8 楼

先序想不出来，后序：每个节点保存子树的最大最小值，后序遍历先访问两个字节点，
再判断node->left->Max < node.value < node->left->Min;

n*w2011-11-24 08:11

9 楼

这样做复杂度是O(n^2)。
比较好的方法是top-down。用min max，递归实现在这里。
http://www.leetcode.com/2010/09/determine-if-binary-tree-is-bin
http://www.mitbbs.com/article_t/JobHunting/31990685.html
如果非递归先序后序做，也是这个思路。
需要改动的是，栈的结构变成，
stack{
Node n;
int min, max;
}
出栈的时候除了得到n，还得refresh min max。
递归中序，需要保留前一个遍历过的节点的值。
referennce或者pointer实现。其实容易错。

【在 s******n 的大作中提到】

: 先序想不出来，后序：每个节点保存子树的最大最小值，后序遍历先访问两个字节点，
: 再判断node->left->Max < node.value < node->left->Min;

q*x2011-11-24 08:11

10 楼

先根很容易啊。

【在 n*******w 的大作中提到】

: 这样做复杂度是O(n^2)。
: 比较好的方法是top-down。用min max，递归实现在这里。
: http://www.leetcode.com/2010/09/determine-if-binary-tree-is-bin
: http://www.mitbbs.com/article_t/JobHunting/31990685.html
: 如果非递归先序后序做，也是这个思路。
: 需要改动的是，栈的结构变成，
: stack{
: Node n;
: int min, max;
: }

n*w2011-11-24 08:11

11 楼

嗯，这个思路，先序后序并没有本质区别。

【在 q****x 的大作中提到】

: 先根很容易啊。

q*x2011-11-24 08:11

12 楼

非递归先序和中序，记住之前一个节点值，应该最简单。

【在 n*******w 的大作中提到】

: 嗯，这个思路，先序后序并没有本质区别。

n*w2011-11-24 08:11

13 楼

先序不一样啊。从栈pop出来，前一个值并不是predecessor。
只有中序是的。

【在 q****x 的大作中提到】

: 非递归先序和中序，记住之前一个节点值，应该最简单。