微软onsite面经，附面试用户体验

很有用啊哈哈哈哈哈

写了写第三题，完全ad-hoc做的。不知有无其他诀窍。

1. def traverse(root):
   
2.     res = [root.val]
   
3.     if root.left:
   
4.         curr = root.left
   
5.     else:
   
6.         curr = root.right
   
7. 
   
8.     while curr != root:
   
9.         res.append(curr.val)
   
10.         # have left child, go left
    
11.         if curr.left:
    
12.             curr = curr.left
    
13.         # have right child, go right
    
14.         elif curr.right:
    
15.             curr = curr.right
    
16.         # no left and right child but have right sibling:
    
17.         elif curr.sibling and curr != root and curr.sibling == curr.parent.right:
    
18.             curr = curr.sibling
    
19.         # no left, right child and don't have right sibling:
    
20.         # two cases:
    
21.             # curr is the right child of parent
    
22.             # curr don't have sibling
    
23.         # case 1 handle, move to parents till it have an right sibling
    
24.         # case 2 handle, move to parents till it have an right sibling
    
25.         else:
    
26.             while curr != root and (not curr.sibling or (curr.sibling and curr.sibling == curr.parent.left)):
    
27.                 curr = curr.parent
    
28.             if curr != root:
    
29.                 curr = curr.sibling
    
30.     return res

复制代码

LCA有O(logH)解法？，是BST的LCA？

szyyn95 发表于 2018-11-19 05:04
Morris Traversal无论如何都会修改树，所以肯定不是，顺便这题很多公司都出过

嘿嘿嘿，morris traversal在遍历的最后会把tree还原的哦

水浅王八多 发表于 2018-11-19 13:12
嘿嘿嘿，morris traversal在遍历的最后会把tree还原的哦

我当然知道…过程中要修改树，我是这个意思

szyyn95 发表于 2018-11-19 21:40
我当然知道…过程中要修改树，我是这个意思

那就。。。傻逼了。。

水浅王八多 发表于 2018-11-20 01:54
那就。。。傻逼了。。

https://www.geeksforgeeks.org/in ... recursion-or-stack/
我一直用的这个解法，据我所知谷歌也考过这个题

szyyn95 发表于 2018-11-20 03:47
https://www.geeksforgeeks.org/inorder-non-threaded-binary-tree-traversal-without-recursion-or-stac ...

多谢多谢，mark了

求LCA log（H）的思路

同求LCA log(H)思路 一般不是O(h)吗？