Facebook Intern面经

pls331

Parent pointer的方法想到了。找到一个关键的parent, 只要找出从当前leaf往上的parent中，第一个走向左孩子的那个node，就是关键node.
关键node的右子树的最小孩子就是下一个。

AmericaDream

parent point 方法有点儿小难，学习了树的遍历竟然可以用O(1)的空间复杂度 厉害

pls331

hlin77 发表于 12-7-2016 06:16 PM
: I1 k" q' d2 V+ u. P用Morris Traversal, 每个有left child的node，他的predecessor用parent pointer连到这儿node，然后就能O（ ...

6 {" ]& p7 B1 d  K! v) I: _可以具体一点吗？Morris Traversal好像在哪儿听过。