j*****y
发帖数: 1071 | 1 在没有 parent指针的情况下,
如果 这个节点没有 右子树，是不是只能从 root search 这个节点，把路径存下来? |
p*****2
发帖数: 21240 | 2
不用。
【在 j*****y 的大作中提到】
: 在没有 parent指针的情况下,
: 如果 这个节点没有 右子树，是不是只能从 root search 这个节点，把路径存下来?
|
j*****y
发帖数: 1071 | 3 二爷那咋搞？不会要来一个 in-order traveral 吧？ 比如
5
/ \
4 6
/
2
\
3
要找 3的 next node
【在 p*****2 的大作中提到】
:
: 不用。
|
j*****y
发帖数: 1071 | 4 没有 parent 指针， 只有 left, right child |
p*****2
发帖数: 21240 | 5
morris
【在 j*****y 的大作中提到】
: 二爷那咋搞？不会要来一个 in-order traveral 吧？ 比如
: 5
: / \
: 4 6
: /
: 2
: \
: 3
: 要找 3的 next node
|
j*****y
发帖数: 1071 | 6 照我的理解 morris 是从root开始做的，等你做到 这个 node的时候，访问了很多节点
吧？
时间代价有点高？
【在 p*****2 的大作中提到】
:
: morris
|
l*****a
发帖数: 14598 | 7 听我的,背不常见的算法不会得到好的comment.
这题用stack就可以给offer了
【在 j*****y 的大作中提到】
: 照我的理解 morris 是从root开始做的，等你做到 这个 node的时候，访问了很多节点
: 吧？
: 时间代价有点高？
|
p*****2
发帖数: 21240 | 8
你如果只是找一个节点的，无论如何都是O(logn)吧？你从root走也无所谓了。一般这
题是
iterator。所以平均O(1)。
【在 j*****y 的大作中提到】
: 照我的理解 morris 是从root开始做的，等你做到 这个 node的时候，访问了很多节点
: 吧？
: 时间代价有点高？
|
c********t
发帖数: 5706 | 9 我觉得存路径是个好主意，用空间换时间。
【在 j*****y 的大作中提到】
: 在没有 parent指针的情况下,
: 如果 这个节点没有 右子树，是不是只能从 root search 这个节点，把路径存下来?
|
j******2
发帖数: 362 | 10 我喜欢这评语，对我的路数。我就是这样的。只会常见算法。哈哈哈哈哈。
【在 l*****a 的大作中提到】
: 听我的,背不常见的算法不会得到好的comment.
: 这题用stack就可以给offer了
|
