题解 | #在二叉树中找到两个节点的最近公共祖先#

算法思想一：递归

解题思路：

若 root 是 o1,o2 的最近公共祖先，则只可能为以下情况之一：

o1 和 o2 在 root 的子树中，且分列 root 的异侧（即分别在左、右子树中）；
o1 = root ，且 o1 在 root 的左或右子树中；
o2 = root，且 o2 在 root 的左或右子树中

考虑通过递归对二叉树进行先序遍历，当遇到节点 o1 或 o2 时返回。从底至顶回溯，当节点 o1, o2 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root

算法流程：

终止条件：
1、当越过叶节点，则直接返回 null ；
2、当 root 等于 o1,o2 ，则直接返回 root ；
递推工作：
1、开启递归左子节点，返回值记为 left ；
2、开启递归右子节点，返回值记为 right ；
3、返回值：根据 left 和 right ，可展开为四种情况；
1、当 left 和 right 同时为空：说明 root 的左 / 右子树中都不包含 o1,o2 ，返回 null ；
2、当 left 和 right 同时不为空：说明 o1,o2 分列在 root 的异侧（分别在左 / 右子树），因此 root为最近公共祖先，返回 root ；
3、当 left 为空，right 不为空：o1,o2 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
1、 o1,o2 其中一个在 root 的右子树中，此时 right 指向 o1（假设为 o1 ）；
2、 o1,o2 两节点都在 root 的右子树中，此时的 right 指向最近公共祖先节点；
4、当 left 不为空， right 为空，返回 root

图解：

代码展示：

Python版本

class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        return self.dfs(root, o1, o2).val

    def dfs(self, root, o1, o2):
        if not root:
            return root
        # 特殊情况，如果o1, o2有一个是根节点，则直接返回根节点
        if root.val == o1 or root.val == o2: 
            return root
        # 从根节点的左子树查找最近公共祖先结点
        left = self.dfs(root.left, o1, o2)
        # 从根节点的右子树查找最近公共祖先结点
        right = self.dfs(root.right, o1, o2)
        # 如果左子树递归结果为空，则返回右子树递归结果
        if not left: return right
        # 反之亦然
        if not right: return left
        # o1, o2 分别在左右子树中，公共祖先是根节点
        return root

复杂度分析

时间复杂度 $O(N)$ ：其中 N 为二叉树节点数；最差情况下，需要递归遍历树的所有节点。
空间复杂度 $O(N)$ ：最差情况下，递归深度达到 N ，系统使用 $O(N)$ 大小的额外空间

算法思想二：哈希表存储父节点

解题思路：

可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 o1 结点开始不断往上跳，并记录已经访问过的节点，再从 o2 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是要找的最近公共祖先。
算法流程：
1、从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
2、从 o1 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
3、同样，我们再从 o2 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 o1 和 o2 的深度最深的公共祖先

代码展示：

JAVA版本

import java.util.*;
/*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
public class Solution {
    /**
         * 
         * @param root TreeNode类 
         * @param o1 int整型 
         * @param o2 int整型 
         * @return int整型
         */
    // 结点祖先集合
    Map parent = new HashMap();
    // 访问结点集合
    Set visited = new HashSet();

    public void dfs(TreeNode root) {
        // 循环遍历左子树 添加祖先集合
        if (root.left != null) {
            parent.put(root.left.val, root.val);
            dfs(root.left);
        }
        // 循环遍历右子树 添加祖先集合
        if (root.right != null) {
            parent.put(root.right.val, root.val);
            dfs(root.right);
        }
    }

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        // 深度遍历添加结点及祖先集合
        dfs(root);
        // 遍历存储 o1 的所有祖先
        while (parent.get(o1) != null) {
            visited.add(o1);
            o1 = parent.get(o1);
        }
        // 如果 o2 是 o1 的祖先路径上的某点，直接返回 o2 即为祖先
        while (parent.get(o2) != null) {
            if (visited.contains(o2)) {
                return o2;
            }
            // 添加 o2 的所有祖先
            o2 = parent.get(o2);
        }
        return root.val;
    }
}

复杂度分析

时间复杂度： $O(N)$ ，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，从 o1 和 o2 节点往上跳经过的祖先节点个数不会超过 N，因此总的时间复杂度为 $O(N)$ 。
空间复杂度： $O(N)$ ，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 $O(N)$ ，哈希表存储每个节点的父节点也需要 $O(N)$ 的空间复杂度，因此最后总的空间复杂度为 $O(N)$ 。