题目主要信息

1、给出两个节点的值

2、给出根节点

3、找到两个节点的最近公共祖先

方法一:递归

具体方法

可以通过递归的方法进行查找每个结点。我们知道，最近公共祖先有两种可能：两个节点分别位于左右两侧；一个节点为该节点，两个节点位于左右两侧。 因此，我们使用findAncestor()函数来进行递归，可以包括五种情况：

1、左右节点均不在，即findAncestor(root.left)==null && findAncestor(root.right)==null，此时应该返回null

2、左节点发现o1，o2，右节点未发现，即findAncestor(root.right)==null，此时，应该寻找左节点

3、右节点发现o1，o2，左节点未发现，即findAncestor(root.left)==null，此时，应该寻找右节点

4、左右节点各发现一个，即findAncestor(root.left)!=null && findAncestor(root.right)!=null，此时，根节点即为结果

5、根节点值等于其中一个节点，即root.val==o1 || root.val==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整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return findAncestor(root, o1, o2).val;
    }
    
    public TreeNode findAncestor(TreeNode root, int o1, int o2){
        if(root == null){
            return null;
        }
        if(root.val == o1 || root.val == o2){  //根节点即为o1或o2
            return root;
        }
        TreeNode left = findAncestor(root.left, o1, o2);
        TreeNode right = findAncestor(root.right, o1, o2);
        
        if(left!=null && right!=null){  //分落在两边
            return root;
        }
        if(left!=null){  //只落在左边
            return left;
        }
        if(right!=null){  //只落在右边
            return right;
        }
        return null;  //未出现
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中n为二叉树的节点数，所有节点只会访问一次
• 空间复杂度：$O(n)O(n)$，其中n为二叉树的节点数，递归深度为树深，最坏情况下为一条链

方法二：非递归

具体方法

非递归的思路较为简单。 通过遍历树，获得所有节点的父节点的hash表，通过对两个节点的链表找到第一个重复节点，即为最近公共祖先。

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<Integer, TreeNode> map = new HashMap<>();  //保存对应父节点
    Set<Integer> set = new HashSet<>();  //查找重复节点
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        dfs(root);
        while(map.containsKey(o1)){
            set.add(o1);
            o1 = map.get(o1).val;
        }
        while(map.containsKey(o2)){
            if(set.contains(o2)){  //出现第一个重复节点，即为最近公共祖先
                return o2;
            }
            o2 = map.get(o2).val;
        }
        return root.val;
    }
    public void dfs(TreeNode node){
        if(node.left!=null){
            map.put(node.left.val, node);
            dfs(node.left);
        }
        if(node.right!=null){
            map.put(node.right.val, node);
            dfs(node.right);
        }
    }
    
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中n为节点个数，dfs访问所有节点
• 空间复杂度：$O(n)O(n)$，其中n为节点个数，hash表容量为n