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 {
    public boolean find = false;
    public void dfs(TreeNode root,ArrayList<Integer> path, int target) {
        if(find || root == null){
            return;
        }
        //加入路径
        path.add(root.val);
        if(root.val == target){
            find = true;
            return;
        }
        //向下查找
        dfs(root.left,path,target);
        dfs(root.right,path,target);
        if(find){
            return;
        }
        //暂时没找到，删除存入的路径，向上回溯
        path.remove(path.size()-1);
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> path1 = new ArrayList<Integer>();
        ArrayList<Integer> path2 = new ArrayList<Integer>();
        //求根节点到目标节点的路径
        dfs(root,path1,o1);
        //重置flag
        find = false;
        dfs(root,path2,o2);
        int res = 0;
        for (int i = 0; i < path1.size() && i < path2.size(); ++i) {
            int x = path1.get(i);
            int y = path2.get(i);
            if (x == y) {
                //保留上一次相等的值
                res = x;
            } else {
                //找到第一个不等的值，则前一个相等的值为最近公共祖先
                break;
            }
        }
        return res;
    }
}

方法一：路径比较法

通过dfs递归获得从根节点到目标节点的路径，然后依次比较找到最后一个相同的节点。

1、定义dfs进行深度遍历，参数为根节点、路径数组、目标节点。需要设置一个标记是否找到目标节点，以便删除最后一个加入的节点，然后回溯。当找到节点或者节点为空时返回，否则将当前节点加入路径，判断是否找到目标节点是则更改标记返回，否则向下遍历。

2、调用dfs将查找两个目标值的路径存起来，注意在找第二个路径之前先将标记复位。

3、遍历两个路径找到最近祖先返回

方法二：递归

二叉树递归找目标节点，若找到其中一个则返回，若一直到叶子节点也没找到则返回-1。向下递归在左右子树中找，若一个在左一个在右则当前节点为最近公共祖先。

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 {
    
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        if(root==null){
            return -1;
        }
        //若o1和o2中
        if(root.val == o1 || root.val == o2){
            return root.val;
        }
        int left = lowestCommonAncestor(root.left,o1,o2);
        int right = lowestCommonAncestor(root.right,o1,o2);
        //左子树找不到则在右子树中
        if(left==-1){
            return right;
        }
        //右子树没找到则在左子树中
        if(right==-1){
            return left;
        }
        //否则是当前节点
        return root.val;
    }
}