fb 热气腾腾（非典型）电面

Renollll · 2019-10-20 08:11:27

jsj 发表于 2019-10-20 07:49
我有个想法，可不可以in order traversal，然后每走一步比较当前的数是不是比前一个数字大。这样只要存前 ...

我其实最开始也是这个想法，但是不借用stack的话，怎么存node的值呢

bubblebobabee · 2019-10-20 08:17:35

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Renollll · 2019-10-20 08:57:22

watertcafe 发表于 2019-10-20 08:17
用morris可以做到O(1)空间
每次存一个inorder prev node就可以了
inorder一步一步走下来每一步都与之 ...

对哦... 之前写遍历的时候没怎么看morris，脑子里都没有可以用morris的概念唉

Jager · 2019-10-20 09:44:00

jsj 发表于 2019-10-20 07:49
我有个想法，可不可以in order traversal，然后每走一步比较当前的数是不是比前一个数字大。这样只要存前 ...

你traverse是用recursion还是iteration呢

jsj · 2019-10-20 23:53:10

Jager 发表于 2019-10-20 09:44
你traverse是用recursion还是iteration呢

我忽略了 traverse本身也需要和树同等高度的空间。。请忽略我。。。楼上的楼上morris才是正解

BestOreo · 2019-10-21 00:16:12

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

BestOreo · 2019-10-21 00:16:33

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Jager · 2019-10-21 02:04:49

jsj 发表于 2019-10-20 23:53
我忽略了 traverse本身也需要和树同等高度的空间。。请忽略我。。。楼上的楼上morris才是正解

嗯，以前只听说过morris没仔细看过，现在要好好研究一下

MrAllenChan · 2019-10-21 03:06:52

https://www.cnblogs.com/grandyang/p/4298435.html
Morris Traversal O(1)解法感觉这个follow up是hard难度了

Renollll · 2019-10-21 03:48:45

MrAllenChan 发表于 2019-10-21 03:06
https://www.cnblogs.com/grandyang/p/4298435.html
Morris Traversal O(1)解法感觉这个follow up是hard ...

感谢！查漏补缺 zszs