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

import java.util.*;

public class Solution {

    // 给定一颗二叉树找到对应两个节点的最近公共祖先
    // 要使用路径记录的话，需要用到回溯的方法，回溯就是出栈
    public boolean flag = false;
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        ArrayList<Integer> path1 = new ArrayList<>();
        ArrayList<Integer> path2 = new ArrayList<>();

        dfs(root,path1,o1);
        // 重置flag，查找下一个
        flag = 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;

    }

    public void dfs(TreeNode root, ArrayList<Integer> path, int o){
        if(flag || root == null){
            return ;
        }
        // 因为都是从最开始的root开始的，所以先直接将root加入路径记录
        path.add(root.val);
        // 因为节点值都不同，可以直接用值比较
        if(root.val == o){
            flag = true;
            return;
        }
        dfs(root.left,path,o);
        dfs(root.right,path,o);
        // 找到之后，表示当前list中记录的节点都是正确的，不需要执行后续的回溯操作
        if(flag) return;
        // 回溯一位，移除掉列表最后一个元素
        path.remove(path.size() - 1);
    }
}