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

#include<iostream>
#include<vector>
using namespace std;
struct node
{
    int l;
    int r;
    int level;
    int parent=-1; 
};

void dfs(vector<node>&arr,int root,int level) //由root开始生成每棵树的level
{
    if(root==0)
        return;
    arr[root].level=level;
    dfs(arr,arr[root].l,level+1);
    dfs(arr,arr[root].r,level+1); 
}

int LCA(vector<node>&arr,int o1,int o2) //寻找o1 o2的最近祖先
{
    while(o1!=o2)
    {
        
        if(arr[o1].level>arr[o2].level)  //o1更低
        {
            o1=arr[o1].parent;
        }
        else if(arr[o1].level<arr[o2].level)
        {
            o2=arr[o2].parent;
        }
        else
        {
             o1=arr[o1].parent;
             o2=arr[o2].parent;  //两者一起向上  
        }
    }
    return o1;
}
int main()
{
    
    int n,root;
    cin>>n>>root;
    vector<node> arr(n+1);
    for(int i=0;i<n;i++)
    {
        int fa,lc,rc;
        cin>>fa>>lc>>rc;
        arr[fa].l=lc;
        arr[fa].r=rc;
        if(lc)
            arr[lc].parent=fa;
        if(rc)
            arr[rc].parent=fa;
    }
    dfs(arr,root,1);
    int m;
    cin>>m;
    while(m--)
    {
        int o1,o2;
        cin>>o1>>o2;
        cout<<LCA(arr,o1,o2)<<endl;   
    }
 
}

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;
    }
}