题解 | #在二叉树中找到两个节点的最近公共祖先#注意不在同一层，和本身就是祖先关系的情况

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        //第一步 层序遍历 放入list中 顺便找出这两个节点以及所在的层数
        List<List<TreeNode>> list = new ArrayList<>();
        TreeNode node1 = null;
        TreeNode node2 = null;
        //这两个节点可能不在一层
        int lineNum1 = -1;
        int lineNum2 = -1;
        boolean isFindNode1 = false;
        boolean isFindNode2 = false;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            if(!isFindNode1){
                lineNum1 += 1;
            }
            if(!isFindNode2){
                lineNum2 += 1;
            }
            int size = q.size();
            List<TreeNode> line = new ArrayList<>();
            for(int i = 0;i<size;i++){
                TreeNode next = q.poll();
                line.add(next);
                if(next.val == o1){
                    node1 = next;
                    isFindNode1 = true;
                }
                if(next.val == o2){
                    node2 = next;
                    isFindNode2 = true;
                }
                if(isFindNode1 && isFindNode2){
                     break;
                }
                if(next.left != null){
                    q.offer(next.left);
                }
                if(next.right != null){
                    q.offer(next.right);
                }
            }
            list.add(line);
        }
        //第二步 从上一层中找他们的父亲  判断是否相等
        if(lineNum2 != lineNum1){
            //不是同一层 先找到同一层的值
            if(lineNum2 > lineNum1){
                node2 = findNode(lineNum1,lineNum2,list,node2);
            } else {
                node1 = findNode(lineNum2,lineNum1,list,node1);
            }
        }
        if(node1 == node2){
            return node1.val;
        }
        int val = findParent(lineNum1,node1,node2,list);
        return val;
        //第三步 重复第二步
    }

    public TreeNode findNode(int smallNum,int bigNum,List<List<TreeNode>> list,TreeNode node){
        TreeNode p = node;
        while(bigNum >= smallNum){
            List<TreeNode> l = list.get(bigNum);
            for(int i =0;i<l.size();i++){
                TreeNode next = l.get(i);
                if(next.left == p || next.right == p){
                    p = next;
                    break;
                }
            }
            bigNum --;
        }
        return p;
    }

    public int findParent(int line,TreeNode node1,TreeNode node2, List<List<TreeNode>> list){
        //从上一层中找到他们的父亲并对比
        TreeNode p1 = null;
        TreeNode p2 = null;
        List<TreeNode> l = list.get(line - 1);
        for(int i =0;i<l.size();i++){
            TreeNode next = l.get(i);
            if(next.left == node1 || next.right == node1){
                p1 = next;
            }
            if(next.left == node2 || next.right == node2){
                p2 = next;
            }
        }
        if(p1 == p2){
            return p1.val;
        } else {
            int nextLine = line -1;
            return findParent(nextLine,p1,p2,list);
        }
    }
}