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

import java.util.*;
import java.io.*;
class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.value = val;
    }
}

    public static TreeNode lowestAncestor(TreeNode head, TreeNode o1, TreeNode o2) {
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        TreeNode left = lowestAncestor(head.left, o1, o2);
        TreeNode right = lowestAncestor(head.right, o1, o2);
        if (left != null && right != null) {
            return head;
        }
        return left != null ? left : right;
    }
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        TreeNode root = new TreeNode(Integer.parseInt(params[1]));
        HashMap<Integer ,TreeNode > map = new HashMap<>();
        map.put(root.value , root);
        for(int i = 0 ; i < n ;i++){
            params = br.readLine().split(" ");
            int val = Integer.parseInt(params[0]);
            TreeNode node = map.get(val);
            int leftval = Integer.parseInt(params[1]);
            int rightval = Integer.parseInt(params[2]);
            if(leftval != 0){
                node.left = new TreeNode(leftval);
                map.put(leftval,node.left);
            }
            if(rightval != 0){
                node.right = new TreeNode(rightval);
                map.put(rightval,node.right);
            }
        }
        params = br.readLine().split(" ");
        TreeNode o1 = map.get(Integer.parseInt(params[0]));
        TreeNode o2 = map.get(Integer.parseInt(params[1]));
        TreeNode ancestor = lowestAncestor(root, o1, o2);
        System.out.println(ancestor.value);
    }
}