递归求树中任意两个节点的最近公共祖先

整个题目其实只需要写出lca函数就OK了，但是前面根据输入构建树等一系列操作，还是挺恶心的，写得挺累，但是感觉没什么意义。

import java.util.*;

public class Main {
    private static TreeNode p = null;
    private static TreeNode q = null;

    /** 
    * 递归的求解
    * 1：p,q都在根节点左子树上，最近公共祖先在左子树上的某个节点
    * 2：p,q都在根节点右子树，最近公共祖先为右子树上的某个节点
    * 3：p,q分别在左右子树上，最近公共祖先为根节点
    */
    private static TreeNode lca(TreeNode root) {
        if(root == null || q == null || p == null) {
            return null;
        }
        if(root == p || root == q) return root;
        TreeNode left = lca(root.left);
        TreeNode right = lca(root.right);
        if(left != null && right != null) return root;
        return left == null ? right : left;
    }

    private static void buildTree(Map<Integer,List<Integer>> treeMap, TreeNode root, int pVal, int qVal) {
        if(root == null) return;
        int rootVal = root.val;
        List<Integer> nodeRecord = treeMap.get(rootVal);
        int leftVal = nodeRecord.get(1);
        int rightVal = nodeRecord.get(2);
        TreeNode left = leftVal == 0 ? null : new TreeNode(root, null, null, leftVal);
        TreeNode right = rightVal == 0 ? null : new TreeNode(root, null, null, rightVal);
        root.left = left;
        root.right = right;
        // 这里判断root的值和pVal qVal是否相等，用于找到这两个节点
        if(pVal == root.val) p = root;
        if(qVal == root.val) q = root;
        buildTree(treeMap, left, pVal, qVal);
        buildTree(treeMap, right, pVal, qVal);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        public TreeNode(TreeNode parent, TreeNode left, TreeNode right, int val){
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int rootVal = scanner.nextInt();
        Map<Integer, List<Integer>> treeMap = new HashMap();
        for(int i = 0; i < n; i++) {
            List<Integer> nodeList = new ArrayList();
            for(int j = 0; j < 3; j++) {
                nodeList.add(scanner.nextInt());
            }
            treeMap.put(nodeList.get(0), nodeList);
        }
        int pVal = scanner.nextInt();
        int qVal = scanner.nextInt();
        TreeNode root = new TreeNode(null, null, null, rootVal);
        buildTree(treeMap, root, pVal, qVal);
        TreeNode node = lca(root);
        if(node == null) System.out.println(0);
        System.out.println(node.val);
    }
}