由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - LC的BST iterator到底要考察什么?
相关主题
这周一的G家onsite,虽然挂了,还是发个面筋攒人品吧G电面面经:BT的iterator inorder traversal
BST 节点的下一个数谁有较好的iterative后序遍历binary tree的代码?
树 inorder下个节点最好办法是啥我发现我竟然学会了12种tree traversal的办法
FB 上周2电面请问怎样写没有parent pointer的BST iterator?
问道题目 Map的iterator转一些我blog上一些常见的二叉树面试问题和总结
【代发】g家面筋攒人品,amazon一面经历
请问leetcode的Binary Search Tree Iterator链表中每三个数逆转的题?
说说面了几个老印的体会考算法可以用stl吗?
相关话题的讨论汇总
话题: bst话题: 节点话题: iterator话题: lc话题: hasnext
进入JobHunting版参与讨论
1 (共1页)
A*******e
发帖数: 2419
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*****h
发帖数: 423
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****z
发帖数: 52
3
楼主 你理解错题意了
题意不是让你把所有的节点遍历出来 是要你写一个iterator() iterator只会返回下
一个节点 当存在无数个节点时 你那样写根本就没有结果 而iterator可以返回节点
x******r
发帖数: 3489
4


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

A*******e
发帖数: 2419
5
这里的BST没有父指针,怎么返回下一个节点?
另外BST的节点当然不会是无数个。

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

B********t
发帖数: 147
6
morris traversal

【在 A*******e 的大作中提到】
: 这里的BST没有父指针,怎么返回下一个节点?
: 另外BST的节点当然不会是无数个。

b*****n
发帖数: 618
7
可以用stack,参考LC的iterative traversal的方法

【在 A*******e 的大作中提到】
: 这里的BST没有父指针,怎么返回下一个节点?
: 另外BST的节点当然不会是无数个。

b*****n
发帖数: 618
8
not a good idea
这样会改变原来tree的结构

【在 B********t 的大作中提到】
: morris traversal
A*******e
发帖数: 2419
9
所以iterator初始化到最小节点,next()就是iterative traversal里走一步?这题出
的很生硬啊。

【在 b*****n 的大作中提到】
: 可以用stack,参考LC的iterative traversal的方法
b*****n
发帖数: 618
10
差不多就这样吧,不过也不一定一开始就要初始化到最小节点,
只要能保证next()平均O(1)就行了。
这个题我被FB问到,这样就过了。。。

【在 A*******e 的大作中提到】
: 所以iterator初始化到最小节点,next()就是iterative traversal里走一步?这题出
: 的很生硬啊。

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

【在 b*****n 的大作中提到】
: 差不多就这样吧,不过也不一定一开始就要初始化到最小节点,
: 只要能保证next()平均O(1)就行了。
: 这个题我被FB问到,这样就过了。。。

w******5
发帖数: 7
12
这个题和iterative遍历树差不多,应该是考察stack的使用吧。

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****z
发帖数: 52
13

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

【在 A*******e 的大作中提到】
: 这里的BST没有父指针,怎么返回下一个节点?
: 另外BST的节点当然不会是无数个。

1 (共1页)
进入JobHunting版参与讨论
相关主题
考算法可以用stl吗?问道题目 Map的iterator
怎么提高BST traversal efficiency?【代发】g家面筋
问tree的iterative traversal请问leetcode的Binary Search Tree Iterator
如何判断两个BST的元素是一样的?说说面了几个老印的体会
这周一的G家onsite,虽然挂了,还是发个面筋攒人品吧G电面面经:BT的iterator inorder traversal
BST 节点的下一个数谁有较好的iterative后序遍历binary tree的代码?
树 inorder下个节点最好办法是啥我发现我竟然学会了12种tree traversal的办法
FB 上周2电面请问怎样写没有parent pointer的BST iterator?
相关话题的讨论汇总
话题: bst话题: 节点话题: iterator话题: lc话题: hasnext