LCA Tarjan Java实现

https://blog.csdn.net/qq_36799943/article/details/78250697 这个图里的子树讲的比较好
https://www.cnblogs.com/zl1991/p/13094997.html 代码的思路借鉴了一些这篇文章

dfs序的主要作用就是将一个子树变成序列上的一个连续区间。
https://www.zhihu.com/question/46440863/answer/2265938163?utm_id=0

import java.util.*;

class TreeNode {
    public int val;
    public List<TreeNode> children;

    public TreeNode(int val) {
        this.val = val;
        children = new ArrayList<>();
    }
}

class TarjanLCA {
    int[] parent; // 并查集的代表元数组
    boolean[] visited; // 是否已访问
    int ans; // 存储每个单个的LCA
    int[] query; // 存储每个查询的参数

    public int findLCA(TreeNode root, int[] query) {
        // 初始化参数
        this.parent = new int[100];
        this.visited = new boolean[100];
        this.query = query;
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        // 预处理节点深度并建图
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode u) {
        for (TreeNode child : u.children) {
            if (!visited[child.val]) {
                dfs(child);
                union(u.val, child.val);
                visited[child.val] = true;
            }
        }
        if (u.val == query[0] && visited[query[1]]) {
            ans = find(query[1]);
            return;
        } else if (u.val == query[1] && visited[query[0]]) {
            ans = find(query[0]);
            return;
        }
    }

    private int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return find(parent[x]);
    }

    // 默认父节点为x
    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.children.add(new TreeNode(2));
        root.children.add(new TreeNode(3));
        root.children.get(0).children.add(new TreeNode(4));
        root.children.get(0).children.add(new TreeNode(5));
        root.children.get(1).children.add(new TreeNode(6));
        root.children.get(1).children.add(new TreeNode(8));
        root.children.get(1).children.get(0).children.add(new TreeNode(7));
        root.children.get(1).children.get(1).children.add(new TreeNode(9));

        int[] query = {7,9};
        int ans = new TarjanLCA().findLCA(root, query);
        System.out.println(ans);
    }
}