databricks电面过社招 求点米

两轮 店面都是经典题

1. 请用O(1)空间复杂度做inorder trave

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

:30):
有pareht指针的树

charleskaka 发表于 2020/02/26 13:15:21
请问楼主如果不用morris怎么做到o(1)traverse？祝顺利！

补充下是有parent指针的
我是用next inorder的方法做的，只可能在右下侧最左边，或者parent判定为左支

更好的做法可以在stackoverflow找到

求米亚

yangmyfly 发表于 2020-2-26 13:30
补充下是有parent指针的
我是用next inorder的方法做的，只可能在右下侧最左边，或者parent判定为左支

其实就是stack稍微改变下嘛 stack的pop本来就是存immediate parent的

yangmyfly 发表于 2020-2-26 13:30
补充下是有parent指针的
我是用next inorder的方法做的，只可能在右下侧最左边，或者parent判定为左支

我在Stack Overflow只搜到morris traversal，请问你的key word是什么？

请问楼主如果不用morris怎么做到o(1)traverse？祝顺利！

请问是BST还是普通的binary tree，谢谢

szhudl 发表于 2020/02/26 18:00:10
请问是BST还是普通的binary tree，谢谢

普通， 没有区别的

有parent 指针是不是就可以用类似 stack 的那个逻辑，只是用parent 指针代替stack的作用

qizhong19920114 发表于 2020/02/27 02:12:49
有parent 指针是不是就可以用类似 stack 的那个逻辑，只是用parent 指针代替stack的作用

请看离口next inorder的做法，求点米

楼主 离口next inorder题号是哪个啊，没找到相关的，以加大米

MonkeyBoss 发表于 2020/03/01 16:26:09
楼主 离口next inorder题号是哪个啊，没找到相关的，以加大米

Successor of inorder, 这个写法不是面试官要的标答，标答请自己在stackoverflow上照