二棵树某两个节点的公共祖先。

1. 如果是有parent指针的树，可以转化成 求两个链表第一个公共节点的问题。

对于无parent指针普通二叉树（假定这两个节点一定在树中，否则需要先遍历一边树查找是否存在该节点）

　　1. （剑指offer的解法），先用一定的空间记录从根节点到两个节点各自的路径，然后找这两个路径最后一个相交的节点。

　　2.  CC150，递归求解。

/**
    假定已经得知p、q 两节点一定在树中i
*/

TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
    if(root==null)
        return null;
    if(root==p||root==q)
        return root;
    
    TreeNode left = commonAncestor(root.left,p,q);
    TreeNode right= commonAncestor(root.right,p,q);
    
    if(left!=null&&right!=null){
        return root;
    }
    else if(left!=null){
        return left;
    }
    else if(right!=null){
        return right;
    }
    else
        return null;
    
}