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

这种题非常简单，总之就是两个字，先层序遍历，目的是记录节点的值，并记下两个节点的位置，找到后结束遍历，上溯查找即可，所谓上溯，就是除以二变成父节点的下标，直到两个相当，此时这个坐标就是最近公共节点的值。
代码如下：

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<Integer> list = new ArrayList<>();
        List<TreeNode> level = new LinkedList<>();
        level.add(root);
        int cnt = 0;
        int index1 = 0;
        int index2 = 0;
        while(cnt<2){
            for(TreeNode node:level){
                if(node!=null){
                   list.add(node.val);
                }else{
                    list.add(null);
                }
                if(node!=null&&(node.val==o1||node.val==o2)){
                    if(node.val==o1){
                        index1 = list.size();
                    }else{
                        index2 = list.size();
                    }
                    cnt++;
                }
            }
            List<TreeNode> tempLevel = new LinkedList<>();
            for(TreeNode node:level){
                if(node==null){
                    tempLevel.add(null);
                    tempLevel.add(null);
                }else {
                    tempLevel.add(node.left);
                    tempLevel.add(node.right);
                }
            }
            level = tempLevel;
        }
//         System.out.println(list+"");
        while(index1!=index2){
            if(index1>index2){
                index1 = index1/2;
            }else{
                index2 = index2/2;
            }
        }
        return list.get(index1-1);
    }

}