LC的BST iterator到底要考察什么？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

LC的BST iterator到底要考察什么？

LC的BST iterator到底要考察什么？# JobHunting - 待字闺中

A*e2015-06-21 07:06

1 楼

给的BST节点没有父指针。然后有下面的要求：
Note: next() and hasNext() should run in average O(1) time and uses O(h)
memory, where h is the height of the tree.
试着写了一个版本，直接周游BST，把结果存在数组里，然后hasNext()和next()都是O(
1)和O(1)，居然也过了。感觉在作弊。

w*h2015-06-21 07:06

2 楼

这个好像不是O(h) memory

O(

【在 A*******e 的大作中提到】

: 给的BST节点没有父指针。然后有下面的要求：
: Note: next() and hasNext() should run in average O(1) time and uses O(h)
: memory, where h is the height of the tree.
: 试着写了一个版本，直接周游BST，把结果存在数组里，然后hasNext()和next()都是O(
: 1)和O(1)，居然也过了。感觉在作弊。

y*z2015-06-21 07:06

3 楼

楼主你理解错题意了
题意不是让你把所有的节点遍历出来是要你写一个iterator() iterator只会返回下
一个节点当存在无数个节点时你那样写根本就没有结果而iterator可以返回节点

x*r2015-06-21 07:06

4 楼

【在 y****z 的大作中提到】

: 楼主你理解错题意了
: 题意不是让你把所有的节点遍历出来是要你写一个iterator() iterator只会返回下
: 一个节点当存在无数个节点时你那样写根本就没有结果而iterator可以返回节点

A*e2015-06-21 07:06

5 楼

这里的BST没有父指针，怎么返回下一个节点？
另外BST的节点当然不会是无数个。

【在 y****z 的大作中提到】

B*t2015-06-21 07:06

6 楼

morris traversal

【在 A*******e 的大作中提到】

: 这里的BST没有父指针，怎么返回下一个节点？
: 另外BST的节点当然不会是无数个。

b*n2015-06-21 07:06

7 楼

可以用stack，参考LC的iterative traversal的方法

【在 A*******e 的大作中提到】

: 这里的BST没有父指针，怎么返回下一个节点？
: 另外BST的节点当然不会是无数个。

b*n2015-06-21 07:06

8 楼

not a good idea
这样会改变原来tree的结构

【在 B********t 的大作中提到】

: morris traversal

A*e2015-06-21 07:06

9 楼

所以iterator初始化到最小节点，next()就是iterative traversal里走一步？这题出
的很生硬啊。

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

: 可以用stack，参考LC的iterative traversal的方法

b*n2015-06-21 07:06

10 楼

差不多就这样吧，不过也不一定一开始就要初始化到最小节点，
只要能保证next()平均O(1)就行了。
这个题我被FB问到，这样就过了。。。

【在 A*******e 的大作中提到】

: 所以iterator初始化到最小节点，next()就是iterative traversal里走一步？这题出
: 的很生硬啊。

A*e2015-06-21 07:06

11 楼

这个真有点屠龙之技的意思，不如直接问stl map的iterator，那个还实用些。BST没必
要省略父指针。这点内存节省和多出的编程开销比，其实不划算。

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

: 差不多就这样吧，不过也不一定一开始就要初始化到最小节点，
: 只要能保证next()平均O(1)就行了。
: 这个题我被FB问到，这样就过了。。。

w*52015-06-21 07:06

12 楼

这个题和iterative遍历树差不多，应该是考察stack的使用吧。

O(

【在 A*******e 的大作中提到】

y*z2015-06-21 07:06

13 楼

不需要父节点
这题考的其实是stack +遍历
iterator的用处是不需要知道全部节点就能尽快返回下一个节点
或者你假设一个bst有一亿个节点如果全部遍历估计要几个小时
用stack可以尽快取出一个节点如果遍历到null了就要adjust 然后又发现新的节点
这题很简单的

【在 A*******e 的大作中提到】

: 这里的BST没有父指针，怎么返回下一个节点？
: 另外BST的节点当然不会是无数个。