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

题目描述： 题目要求简单易懂，就是在一棵二叉树中找到给定的o1和o2这两个节点的最近的公共祖先。

我们想想，两个节点的最近的公共祖先，无外乎就以下几种情况。
第一种，o1和o2恰好分布在根节点root的两侧，那么最近的公共祖先即为根节点root。

第二种，o1和o2分布在根节点的同一侧，那么则会出现两种情况。

① 首先，出现如下图这种情况，则可以转变为第一种情况，o1和o2分布在了值为5的这个节点的两侧。那么此时o1和o2的最近公共祖先则为值为5这个节点。

② o1和o2恰好的父子节点的关系，那么此时它们最近的公共祖先则为那个父节点的节点。

所以，基于上面情况的分析，我们可以使用递归的方式来解决这道题目。

方法一:递归
直接从根节点往下寻找，如果当前节点既不是o1也不是o2。

• 从左侧寻找o1和o2，当找到其中一个则返回
• 从右侧寻找o1和o2，当找到其中一个则返回
  如果当前节点为o1或者o2，则证明当前节点为两者的最近公共祖先。

  例如，当前节点是o1，那么此时o2必定是o1的子孙节点。所以o1即为两者的最近公共祖先。

代码：

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return LRD(root,o1,o2).val;
    }

    public TreeNode LRD(TreeNode root, int o1, int o2){
        // 找到o1或者o2，或者遍历到尽头还没找到则返回root(null)
        if(root == null || root.val == o1 || root.val == o2)
            return root;
        // 朝着root节点的左边去寻找o1，o2
        TreeNode left = LRD(root.left,o1,o2);
        // 朝着root节点的右边去寻找o1，o2
        TreeNode right = LRD(root.right,o1,o2);

        // 如果root节点的左边没有o1或者o2，则证明o1和o2分布在二叉树的右侧
        // 那么此时则直接返回right, right为先找到的节点 o1或者o2
        if(left == null)
            return right;
        // 如果root节点的右边没有o1或者o2，则证明o1和o2分布在二叉树的左侧
        // 那么此时则直接返回left, left为先找到的节点 o1或者o2
        if(right == null)
            return left;

        // 否则，当前节点即为o1和o2的最近公共祖先，此时o1和o2分布在root两侧
        return root;
    }

复杂度分析:
时间复杂度：。n为二叉树的结点数，需要遍历n次。
空间复杂度：。当二叉树退化成链表的时候，此时递归深度为n。

方法二:使用哈希表存储父节点
我们不妨换个思路，因为题目主要就是要找出两个节点的最近公共祖先，出现的所有情况如题目开头分析。所以我们可以使用一个哈希表，先存储所有的节点的父节点。然后利用题目给出的两个节点o1，o2，先取o1，遍历找出其的所有父节点(即父节点的节点都找出来)，并记录起来。接着我们取o2，遍历找出其父节点，如果在遍历的过程中，发现其父节点已经访问过了，那么此时这个访问过的节点必定就是两者的最近的公共祖先了。

代码：

    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // 先调用dfs方法
        dfs(root);
        // 创建两个节点，值为o1，o2
        TreeNode node1 = new TreeNode(o1);
        TreeNode node2 = new TreeNode(o2);
        // 对值为o1的这个节点，向上遍历找出其所有父节点(祖先节点)
        while (node1 != null) {
            visited.add(node1.val);
            // 向上
            node1 = parent.get(node1.val);
        }
        // 向上遍历值为o2的节点
        while (node2 != null) {
            // 如果已经访问过了，证明这个节点就是两个节点的最近公共祖先
            if (visited.contains(node2.val)) {
                return node2.val;
            }
            // 向上
            node2 = parent.get(node2.val);
        }
        return root.val;

    }

    // dfs先将整棵树中的节点与其父节点的信息记录起来
    public void dfs(TreeNode root) {
        // 遍历最子树
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        // 遍历右子树
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

复杂度分析:
时间复杂度：。n为二叉树的结点数，需要遍历n次。
空间复杂度：。当二叉树退化成链表的时候，此时递归深度为n。