原始题目：剑指 Offer 68 - II. 二叉树的最近公共祖先 (opens new window)

方法一：哈希表

如果能知道每个节点的父节点，那么就可以通过 $p$，$q$ 向上追溯找到最近的共同的父节点。因为题目中的二叉树并没有 $parent$ 指针，所以需要使用哈希表来映射子节点到父节点的关系。

拿到子节点和父节点的映射关系后，从 $p$ 开始往上访问父节点，并记录起来。然后再从 $q$ 开始往上遍历父节点，如果碰到已访问的节点，那么这个节点就是最近公共父节点。

代码：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    Map<TreeNode, TreeNode> parentMap = new HashMap<>();
    Set<TreeNode> visited = new HashSet<>();
    getParentMap(parentMap, root, null);
    while(p != null) {
        visited.add(p);
        p = parentMap.get(p);
    }
    while(q != null) {
        if(visited.contains(q)) {
            return q;
        }
        q = parentMap.get(q);
    }
    return null;
}

private void getParentMap(Map<TreeNode, TreeNode> map, TreeNode node, TreeNode parent) {
    if (node == null) {
        return;
    }
    map.put(node, parent);
    getParentMap(map, node.left, node);
    getParentMap(map, node.right, node);
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 为二叉树的节点个数。最差情况下，树退化成 “^” 型链表 ，最近公共父节点为根节点。
• 空间复杂度$O(N)$：最差情况下，需要存储所有的树节点。

方法二：深度优先搜索

后序遍历二叉树，定义 $f_x$ 表示 x 节点的子树是否包含 p 或者 q。如果包含为 true，否则为 false。那么最近的公共祖先一定满足如下条件：

$$(f_{lson} \space \&\& \space f_{rson}) \space || \space (( x.val == p.val \space || \space x == q.val ) \space \&\& \space(f_{lson} \space || \space f_{rson}))$$

$lson$ 和 $rson$ 分别表示 x 的左右子节点。这个条件表示

• 如果 $p$ 或者 $q$ 分别散布在 x 的左节点或者子节点，那么 $x$ 就是 $p$，$q$ 的最近公共父节点。
  • 比如 $p$ 在 $x$ 的左子树，$q$ 在 $x$ 的右子树。
• $p$ 或者 $q$ 就是 $x$ 节点本身，那么就看另一个节点是否在 x 的子树中
  • 比如 $x$ 本身就是 $p$ 节点了，那么就看 $q$ 是否在 $p$ 的子树中。

因为是自底向上的遍历，所以找到的公共祖先的深度一定是最大的。

代码：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    findSon(root, p, q);
    return this.ans;
}

/**
 * 判断 root 中是否包含 p 或者 q
 */
private boolean findSon(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) {
        return false;
    }
    boolean inLeft = findSon(root.left, p, q);
    boolean inRight = findSon(root.right, p, q);
    if((inLeft && inRight) ||
            ((root.val == p.val || root.val == q.val) && (inLeft || inRight))){
        this.ans = root;
    }
    return inLeft || inRight || (root.val == p.val) || (root.val == q.val);
}

复杂度分析

• 时间复杂度$O(N)$：其中，$N$ 为二叉树的节点数。二叉树的节点有且只会被访问一次，因此时间复杂度为 $O(N)$。
• 空间复杂度$O(N)$：最差情况下，树退化成链表，需要 $O(N)$ 递归栈空间。