FB 8/19 面经

tree的recursion换成iteration处理，一般用stack都能解决吧（相当于手动用stack模拟recursion）。感觉这题可以是一个样的做法，换成post order访问，这样处理每个node的时候，左右孩子的信息都有了，而且最后一个处理的node一定是tree root。

最近这个题很高频啊，其实dfs遍历，返回的时候返回lca和depth，每个node如果有大于一个子节点的depth相同就返回这个node，如果有一个子节点depth更深就返回个子节点lca，这个o(n)就可以了

楼主有空分享分享design题呀

这题好高频，前两天才看到有人面一样的

zzh730 发表于 2016-8-20 12:20
最近这个题很高频啊，其实dfs遍历，返回的时候返回lca和depth，每个node如果有大于一个子节点的depth相同就 ...

这个貌似get到了， 贴一个我的代码， 是这么个意思吗？

1. TreeNode* dfs(TreeNode * root, int & depth){
   
2.     if(!root){
   
3.         depth = 0;
   
4.         return NULL;
   
5.     }
   
6.    
   
7.     int ldepth, rdepth;
   
8.     TreeNode * left = dfs(root->left, ldepth);
   
9.     TreeNode * right = dfs(root->right, rdepth);
   
10.     depth = 1 + max(ldepth, rdepth);
    
11.    
    
12.     if(ldepth == rdepth) return root;
    
13.     else if(ldepth < rdepth) return right;
    
14.     else return right;
    
15. }
    
16. 
    
17. int commonAncestor(TreeNode * root){
    
18.     int depth;
    
19.     TreeNode* LCA = dfs(root, depth);
    
20.     cout << "Tree depth:" << depth << endl;
    
21.     return LCA->val;
    
22. }
    

复制代码

一个很naive的想法， 可不可以BFS找到deepest nodes， 同时把每一个node记录其parent。
每个 node向上返回一步， 把它们的parent用一个set来记录， 迭代， 当set的 size为1的时候就是他们的lowest common ancestor。

Lilian1109 发表于 2016-8-23 03:16
这个貌似get到了， 贴一个我的代码， 是这么个意思吗？

是的，题里是多叉树，稍稍改下就好了

Lilian1109 发表于 2016-8-23 03:16
这个貌似get到了， 贴一个我的代码， 是这么个意思吗？

这个代码写的很好！
如果不让用recursion，可以用一个stack来做post order travesal，顺便把左右子树的高度算出来比较，keep track这个左右子树一样高度最大值的父节点，即为所求。

chen6145 发表于 2016-8-21 01:19
楼主有空分享分享design题呀

design  pocketmon ,  google search suggestion.

感觉这个可以DFS解。返回值为当前子树上最深叶子节点的深度，和当前子树上的最深叶子节点的lca。

1. private static class Solution {
   
2.         private class ReturnVal {
   
3.             public int depth;   //The depth of the deepest leaves on the current subtree
   
4.             public TreeNode lca;//The lca of the deepest leaves on the current subtree
   
5. 
   
6.             public ReturnVal(int d, TreeNode n) {
   
7.                 depth = d;
   
8.                 lca = n;
   
9.             }
   
10.         }
    
11. 
    
12.         public TreeNode LowestCommonAncestorOfDeepestLeaves(TreeNode root) {
    
13.             ReturnVal res = find(root, 0);
    
14.             return res.lca;
    
15.         }
    
16. 
    
17.         private ReturnVal find(TreeNode root, int depth) {
    
18.             if(root == null) {
    
19.                 return new ReturnVal(-1, null);
    
20.             } else {
    
21.                 ReturnVal lRes = find(root.left, depth+1);
    
22.                 ReturnVal rRes = find(root.right, depth+1);
    
23. 
    
24.                 if(lRes.depth == rRes.depth) {
    
25.                     return new ReturnVal(lRes.depth==-1?depth:lRes.depth, root);
    
26.                 } else {
    
27.                     return new ReturnVal(Math.max(rRes.depth, lRes.depth), rRes.depth>lRes.depth?rRes.lca:lRes.lca);
    
28.                 }
    
29.             }
    
30.         }
    
31.     }

复制代码