在二叉树中找到两个节点的最近公共祖先(进阶)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int rootVal = sc.nextInt();
        TreeNode root = buildTree(sc, n, rootVal);
        Record record = new Record(root);
        int m = sc.nextInt();
        StringBuilder cache = new StringBuilder();
        while (m-- > 0) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            cache.append(record.query(u, v)).append("\n");
        }
        System.out.println(cache);
    }


    private static TreeNode buildTree(Scanner sc, int n, int rootVal) {
        Map<Integer, TreeNode> map = new HashMap<>();
        while (n-- > 0) {
            int fa = sc.nextInt();
            int lch = sc.nextInt();
            int rch = sc.nextInt();
            TreeNode faNode = map.get(fa);
            if (faNode == null) {
                faNode = new TreeNode(fa);
                map.put(fa, faNode);
            }
            if (lch != 0) {
                TreeNode lchNode = map.get(lch);
                if (lchNode == null) {
                    lchNode = new TreeNode(lch);
                    map.put(lch, lchNode);
                }
                faNode.left = lchNode;
            }
            if (rch != 0) {
                TreeNode rchNode = map.get(rch);
                if (rchNode == null) {
                    rchNode = new TreeNode(rch);
                    map.put(rch, rchNode);
                }
                faNode.right = rchNode;
            }
        }
        return map.get(rootVal);
    }
}

class Record {
    private Map<Integer, HashMap<Integer, Integer>> map;  // a b c: a和b的父节点是c

    public Record(TreeNode head) {
        map = new HashMap<>();
        initMap(head);
        setMap(head);
    }

    private void initMap(TreeNode head) {
        if (head == null) {
            return;
        }
        map.put(head.val, new HashMap<>());
        initMap(head.left);
        initMap(head.right);
    }

    private void setMap(TreeNode head) {
        if (head == null) {
            return;
        }
        headRecord(head.left, head);
        headRecord(head.right, head);
        subRecord(head);
        setMap(head.left);
        setMap(head.right);
    }

    private void headRecord(TreeNode son, TreeNode head) {
        if (son == null) {
            return;
        }
        map.get(son.val).put(head.val, head.val);
        headRecord(son.left, head);
        headRecord(son.right, head);
    }

    private void subRecord(TreeNode head) {
        if (head == null) {
            return;
        }
        preLeft(head.left, head.right, head);
        subRecord(head.left);
        subRecord(head.right);
    }

    private void preLeft(TreeNode left, TreeNode right, TreeNode head) {
        if (left == null) {
            return;
        }
        preRight(left, right, head);
        preLeft(left.left, right, head);
        preLeft(left.right, right, head);
    }

    private void preRight(TreeNode left, TreeNode right, TreeNode head) {
        if (right == null) {
            return;
        }
        map.get(left.val).put(right.val, head.val);
        preRight(left, right.left, head);
        preRight(left, right.right, head);
    }

    public int query(int o1, int o2) {
        if (o1 == o2) {
            return o1;
        }
        if (map.containsKey(o1) && map.get(o1).containsKey(o2)) {
            return map.get(o1).get(o2);
        }
        if (map.containsKey(o2) && map.get(o2).containsKey(o1)) {
            return map.get(o2).get(o1);
        }
        return -1;
    }
}