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

import java.io.*;
import java.util.*;
public class Main {

    static class Node{
        int value;
        Node left;
        Node right;

        public Node(int data){
            this.value=data;
        }
    }

    public static Node lowestAncestor(Node head,Node o1,Node o2){
        if(head==null||head.value==o1.value||head.value==o2.value){
            return head;
        }
        Node left=lowestAncestor(head.left,o1,o2);
        Node right=lowestAncestor(head.right,o1,o2);
        //左右子树都不为空
        if(left!=null&&right!=null){
            return head;
        }

        //左右子树有一个不空
        return left!=null? left:right;
    }


    public static Node createTree(Scanner in, int n){
        int rootValue=in.nextInt();
        Node root=new Node(rootValue);
        HashSet<Node> set=new HashSet<Node>();
        set.add(root);

        //n行读取
        for (int i = 0; i < n; i++) {
            int fatherValue= in.nextInt();
            int leftValue=in.nextInt();
            int rightValue=in.nextInt();
            //遍历
            for (Node e:set){
                //1、比较节点
                if(e.value==fatherValue){
                    //2、建立左右节点
                    Node left= leftValue==0?null:new Node(leftValue);
                    Node right= rightValue==0?null:new Node(rightValue);
                    e.left=left;
                    e.right=right;
                    //3、放入节点
                    if(leftValue!=0){
                        set.add(left);
                    }
                    if(rightValue!=0){
                        set.add(right);
                    }
                    //4、remove
                    set.remove(e);
                    break;
                }
            }

        }


        return root;
    }
    /*
    8 1
    1 2 3
    2 4 5
    4 0 0
    5 0 0
    3 6 7
    6 0 0
    7 8 0
    8 0 0
    4 5
    out:2
    * */
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        Node root=createTree(in,n);

        int v1=in.nextInt();
        int v2=in.nextInt();
        Node o1=new Node(v1);
        Node o2=new Node(v2);

        Node result=lowestAncestor(root,o1,o2);
        System.out.println(result.value);

    }

}