2、求二叉树的任意两个节点的近公共祖先。

　　点评：何谓低公共祖先，如下图所示：节点1和节点7的低公共祖先便是5

　　点评：此题看似简单，实则不简单，下面参考引用《Cracking the Coding Interview》一书上的解法：

　　说简单是因为如果这棵树是二叉查找树，则低公共祖先t必在两个节点p和q的中间处，即p

　　说不简单则是因为如果不是二叉查找树，则我们必须确定这棵树的结点是否包含指向父结点的连接，如此：

　　①当包含指向父结点的连接时，如果每个结点都包含指向父结点的连接，我们可以向上追踪p和q的路径，直至两者相交。

　　不过，这么做可能不符合题目的若干假设，因为它需要满足以下两个条件之一：1)可将结点标记为isVisited;2)可用另外的数据结构如散列表储存一些数据。

　　②不包含指向父结点的连接时，另一种做法是，顺着一条p和q都在同一边的链子，也是说，若p和q都在某结点的左边，到左子树中查找共同祖先。

　　若都在右边，则在右子树中查找共同祖先。要是p和q不在同一边，那表示已经找到第一个共同祖先。

　　这种做法的实现代码如下：

　　[cpp] view plaincopyprint?

　　/* 若p为root的子孙，则返回true */

　　boolean covers(TreeNode root， TreeNode p) {

　　if (root == null) return false;

　　if (root == p) return true;

　　return covers(root.left， p) || covers(root.right， p);

　　}

　　TreeNode commonAncestorHelper(TreeNode root， TreeNode p，

　　TreeNode q) {

　　if (root == null) return null;

　　if (root == p || root == q) return root;

　　boolean is_p_on_left = covers(root.left， p);

　　boolean is_q_on_left = covers(root.left， q);

　　/* 若p和q不在同一边，则返回root */

　　if (is_p_on_left != is_q_on_left) return root;

　　/* 否则是在同一边，遍访那一边 */

　　TreeNode child_side = is_p_on_left ? root.left : root.right;

　　return commonAncestorHelper(child_side， p， q);

　　}

　　TreeNode commonAncestor(TreeNode root， TreeNode p， TreeNode q) {

　　if (!covers(root， p) || !covers(root， q)) { // 错误检查

　　return null;

　　}

　　return commonAncestorHelper(root， p， q);

　　}