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

import java.util.*;

public class Solution {

    // 方法：搜索路径比较
    // 因为题中的二叉搜索树没有相同的结点，因此分别从根节点往下利用二叉搜索树较大的数在右子树，较小的数在左子树，可以轻松找到p、q

    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here

        ArrayList<Integer> listP = new ArrayList<>();
        ArrayList<Integer> listQ = new ArrayList<>();

        recordPath(p,listP,root);
        recordPath(q,listQ,root);
        System.out.println(listP.toString());
        System.out.println(listQ.toString());

        // 根据记录下来的路径找到最后一个重复点，就是最近公共祖先
        int len = Math.min(listP.size(),listQ.size());
        int res = -1;
        for(int i = 0;i<len;i++){
            if(!listP.get(i).equals(listQ.get(i))){
                break;
            }
            res = listP.get(i);
        }

        return res;
    }

    public void recordPath(int num, ArrayList<Integer> list, TreeNode root) {
        TreeNode node = root;
        while(node != null){
            list.add(node.val);
            if(node.val < num){
                node = node.right;
            }else if(node.val > num){
                node = node.left;
            }else if(node.val == num){
                break;
            }
        }
    }
}