给一个 二叉树 ， 求最深节点的最小公共父节点
return .
retrun .
先用 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;
}
1 package fbOnsite;
public class LCA2 {
private class ReturnVal {
public int depth; //The depth of the deepest leaves on the current subtree
public TreeNode lca;//The lca of the deepest leaves on the current subtree
public ReturnVal(int d, TreeNode n) {
depth = d;
lca = n;
}
}
public TreeNode LowestCommonAncestorOfDeepestLeaves(TreeNode root) {
ReturnVal res = find(root);
return res.lca;
}
private ReturnVal find(TreeNode root) {
if(root == null) {
return new ReturnVal(0, null);
} else {
ReturnVal lRes = find(root.left);
ReturnVal rRes = find(root.right);
if(lRes.depth == rRes.depth) {
return new ReturnVal(lRes.depth+1, root);
} else {
return new ReturnVal(Math.max(rRes.depth, lRes.depth)+1, rRes.depth>lRes.depth?rRes.lca:lRes.lca);
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode t1 = new TreeNode(1);
TreeNode t2 = new TreeNode(2);
TreeNode t3 = new TreeNode(3);
TreeNode t4 = new TreeNode(4);
TreeNode t5 = new TreeNode(5);
TreeNode t6 = new TreeNode(6);
TreeNode t7 = new TreeNode(7);
t1.left = t2;
t1.right = t3;
t2.left = t4;
//t3.left = t5;
//t3.right = t6;
t2.right = t7;
LCA sol = new LCA();
TreeNode res = sol.LowestCommonAncestorOfDeepestLeaves(t1);
System.out.println(res.val);
}
}