FB 8/19 面经

请问楼主 面试完后一天有收到填面试feedback的邮件嘛？

zhuhai_ZFC 发表于 2016-8-31 02:05
感觉这个可以DFS解。返回值为当前子树上最深叶子节点的深度，和当前子树上的最深叶子节点的lca。

昨天晚上还和朋友讨论这题来着，思路和你的基本一样~

leyhzm 发表于 2016-8-31 23:27
请问楼主 面试完后一天有收到填面试feedback的邮件嘛？

有填， 就是问 recruiter 专不专业， 有没有人迟到之类的。

lvvvvv 发表于 2016-9-1 11:09
有填， 就是问 recruiter 专不专业， 有没有人迟到之类的。

谢谢！请问LZ面试有结果了嘛？大概面完多久通知结果哒~

是BST 么？ 还是BT

hychin 发表于 2016-8-19 12:16
recursive 直接DFS找最底层最左和最右边的点然后求这两个点的LCA即可，iteration就变成BFS找最后一层的第一 ...

请问如何证明所有最深的叶子结点的LCA就等于最后一层的第一个和最后一个的LCA呢？我感觉直觉上是对的，但是仔细想证明好像又没有办法证明？不知道层主有没有什么好的证明方法？感谢！

zzh730 发表于 2016-8-23 06:19
是的，题里是多叉树，稍稍改下就好了

不对啊，LZ说RECURSION的她也写出来了，人家面试官要的是ITERATION的

同上 这题iterative该怎么做

不是很懂题目。第一个例子不应该是return 1吗？  1不是最小吗

Iteration如下，就是post-order traversal的iterative版本

1. TreeNode *LCA(TreeNode *root)
   
2. {
   
3.     stack<TreeNode *> stk;
   
4.     unordered_map<TreeNode *, pair<TreeNode *, int>> map; //node mapped to (LCA node, height)
   
5.     TreeNode *prev = NULL;
   
6. 
   
7.     TreeNode *node = root;
   
8. 
   
9.     while (!stk.empty() || node) {
   
10.         if (node) {
    
11.             stk.push(node);
    
12.             node = node->left;
    
13.         } else {
    
14.             TreeNode *peek_node = stk.top();
    
15. 
    
16.             if (peek_node->right && prev != peek_node->right)
    
17.                 node = peek_node->right;
    
18.             else {
    
19.                 stk.pop();
    
20.                 //下面比较乱，可以简洁一下
    
21.                 if (!peek_node->left && !peek_node->right)
    
22.                     map[peek_node] = make_pair(peek_node, 1);
    
23.                 else if (peek_node->left && peek_node->right) {
    
24.                     auto left = map[peek_node->left];
    
25.                     auto right = map[peek_node->right];
    
26. 
    
27.                     if (left.second == right.second)
    
28.                         map[peek_node] = make_pair(peek_node, left.second+1);
    
29.                     else if (left.second > right.second)
    
30.                         map[peek_node] = make_pair(left.first, left.second+1);
    
31.                     else
    
32.                         map[peek_node] = make_pair(right.first, right.second+1);
    
33.                 } else {
    
34.                     if (peek_node->left) {
    
35.                         auto left = map[peek_node->left];
    
36.                         map[peek_node] = make_pair(left.first, left.second+1);
    
37.                     } else {
    
38.                         auto right = map[peek_node->right];
    
39.                         map[peek_node] = make_pair(right.first, right.second+1);
    
40.                     }
    
41.                 }
    
42. 
    
43.                 prev = peek_node;
    
44.             }
    
45.         }
    
46.     }
    
47. 
    
48.     return map[root].first;
    
49. }
    

复制代码