databricks电面过社招 求点米

qiuqiushasha 发表于 2020/03/08 04:47:26
其实就是stack稍微改变下嘛 stack的pop本来就是存immediate parent的

但是是o1 space

只能想到类似nextInorder的算法，stackOverFlow也只找到这种。lz能不能再稍微给点提示？谢谢

给你点个赞！

其实就是考虑当visit curr node的时候 有以下几种情况
1. 左subtree还没visit
2.左subtree visited 回来的
3.右subtree上来的

想想怎么把这三种情况区分开
提示  用一个bool记录左边是否visited, 一旦该点左边没visited往左就肯定是先走到最左  且bool变成visited
右边要一直pop上来

请问一下input是任何一个node，还是会提供root node？

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

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