Facebook Intern面经

pls331

Parent pointer的方法想到了。找到一个关键的parent, 只要找出从当前leaf往上的parent中，第一个走向左孩子的那个node，就是关键node.
4 ~: Y6 e: l" H* u% k关键node的右子树的最小孩子就是下一个。

AmericaDream

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

pls331

hlin77 发表于 12-7-2016 06:16 PM
5 q( R) j6 _( u1 z! R" J- o: J/ B用Morris Traversal, 每个有left child的node，他的predecessor用parent pointer连到这儿node，然后就能O（ ...

( z! b! g" w+ C6 E+ g可以具体一点吗？Morris Traversal好像在哪儿听过。