136 二叉树的最近公共祖先

问题描述：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

求解思路：保存从根节点到两个节点的两个路径(使用链表)，再对两个链表进行比较，最后一个相同的节点也就是最近的公共祖先。

public void findCloseAncester(TreeNode root,List<TreeNode>list,List<List<TreeNode>>res,TreeNode p,TreeNode q)
{
if(root==null){return;}
if(root==p||root==q){list.add(root);res.add(list);return;}
list.add(root);
findCloseAncester(root.left,list,res,p,q);
findCloseAncester(root.right,new List<TreeNode>(list),p,q);
}
public TreeNode?FindCloseAncester(TreeNode root)
{
List<List<TreeNode>>res;
findCloseAncester(root,newLinkedList<TreeNode>(),res,p,q);
TreeNode pre=res.get(0).get(0);
for(int i=1;i<res.get(0).size();i++)
{
if(res.get(0).get(i)!=res.get(1).get(i)){break;}
pre=res.get(0).get(i);
}
???????return pre;
}