LCA of Deepest Nodes in Binary Tree - Facebook

https://www.cnblogs.com/EdwardLiu/p/6551606.html

给一个 二叉树 ， 求最深节点的最小公共父节点
     1
  2   3
     5  6    return 3.

       1  
    2   3
4      5 6   retrun 1. 
先用 recursive  ， 很快写出来了， 要求用 iterative 。 时间不够了。。。

Recursion: 返回的时候返回lca和depth，每个node如果有大于一个子节点的depth相同就返回这个node，如果有一个子节点depth更深就返回个子节点lca，这个o(n)就可以了

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

我的想法是要用hashMap<TreeNode, Info>

class Info{

　　int height;

　　TreeNode LCA;

}

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

find lowest common ancestor among deepest nodes in k-nary tree
前⼏几年年的经典题