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

import java.util.*;


public class Solution {

    public boolean flag = false;
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        ArrayList<Integer> listP = new ArrayList<>();
        ArrayList<Integer> listQ = new ArrayList<>();
        dfs(root,listP,p);
        flag = false;
        dfs(root,listQ,q);

        int res = 0;
        for(int i = 0;i<listP.size() && i<listQ.size();i++){
            if(listP.get(i).equals(listQ.get(i))){
                res = listP.get(i);
            }else{
                break;
            }
        }

        return res;

    }

    public void dfs(TreeNode root, ArrayList<Integer> list, int num){

        if(flag || root == null){
            return ;
        }
        // 将根节点添加到路径
        list.add(root.val);
        // 当找到目标节点，将flag=true，表示无需进行回溯操作
        if(root.val == num){
            flag = true;
            return;
        }
        // 遍历左右子树
        dfs(root.left,list,num);
        dfs(root.right,list,num);
        if(flag) return;

        list.remove(list.size() - 1);
    }
}