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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        //普通二叉树：因为没有节点值的大小关系，所以无法通过值的大小判断LCA的位置
        //因此需要通过遍历树来找到o1和o2的位置
        //如果当前节点是o1或o2，则返回当前节点
        //如果o1和o2分别位于当前节点的左右子树，则当前节点为LCA
        //如果o1和o2都位于左子树或右子树中，则继续递归遍历对应的子树
        if(root == null){
            return -1;
        }

        if(root.val == o1 || root.val == o2){
            return root.val;
        }

        //后序遍历树，查找o1，o2位于左右子树
        int left = lowestCommonAncestor(root.left,o1,o2);
        int right = lowestCommonAncestor(root.right,o1,o2);

        if(left != -1 && right !=-1){
            //如果o1和o2分别在左右子树中，说明当前节点即为公共祖先节点
            return root.val;
        }
        
        //如果o1或者o2不在左子树中，返回右子树查找
        if(left == -1){
            return right;
        }
        if(right == -1){
            return left;
        }
        //如果都没有查找到，只有返回不存在
        return -1;
    }

}

解题思路：这道题和二叉搜索树找公共祖先思路相似，但具体执行不同。主要原因是本题所说的二叉树只是一个普通二叉树。搜索二叉树还可以通过判断当前节点与节点o1和o2的值，确定o1和o2位于左子树还是右子树。而本题没有值可以比较，所以需要通过对树的遍历来找到o1和o2的位置。

相似之处：

1.最近公共祖先（LCA）判定：1. 当节点 o1和o2分别在当前节点的左子树/右子树时；2. 当前节点值 = o1/o2.

不同之处：

1.没有节点值大小关系，无法通过值判断公共节点位置；2. 需要进行遍历树，只有当当前节点左右子树返回值均不为特殊值-1时，才能判断当前节点即为公共祖先。// left != -1 && right !=-1