题解 | #二叉搜索树的最近公共祖先#

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 ArrayList<Integer> getPath(TreeNode root,int target){
        ArrayList<Integer> path = new ArrayList<Integer>();
        TreeNode node=root;
        while(node.val != target){
            path.add(node.val);
            if(node.val > target){
                node = node.left;
            }else{
                node = node.right;
            }
        }
        path.add(target);

        return path;
    }
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        ArrayList<Integer> pPath = pPath = getPath(root,p);
        ArrayList<Integer> qPath = qPath = getPath(root,q);
               
        int res = 0;
        for(int i=0;i<pPath.size()&&i<qPath.size();++i){
            int x = pPath.get(i);
            int y = qPath.get(i);
            if(x==y){
                //保留上一次相等的值
                res = x;
            }else{
                //找到第一个不等的值，则前一个相等的值为最近公共祖先
                break;
            }
        }

        return res;
    }
}

方法：比较路径法

通过遍历查询目标节点得到路径，找到第一个不相等的值，则前一个相等的值就是最近公共祖先。

1、定义一个记录查询路径的函数

2、调用函数得到两个路径

3、遍历两个路径，记录相等值

4、找到不等值

5、返回记录值