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的节点当然不会是无数个。
|