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

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // 记录有子元素的节点
        ArrayList<treenode> list = getNode(root);
        for(int i=list.size()-1; i>=0;i--){
            TreeNode node = list.get(i);
            hasO1 = false;
            hasO2 = false;
            preOrder(node, o1, o2);
            if(hasO1 && hasO2){
                return node.val;
            }
        }
        return -1;
    }

    boolean hasO1 = false;
    boolean hasO2 = false;

    public void preOrder(TreeNode root, int o1, int o2){
        if(root!=null){
            if(root.val == o1) hasO1 = true;
            if(root.val == o2) hasO2 = true;
            preOrder(root.left, o1, o2);
            preOrder(root.right, o1, o2);
        }
    }

    public ArrayList<treenode> getNode(TreeNode root){
        ArrayList<treenode> list = new ArrayList<>();
        ArrayList<treenode> queue = new ArrayList<>();
        queue.add(root);
        while(queue.size()!=0){
            TreeNode node = queue.remove(0);
            if(node.left!=null || node.right!=null){
                list.add(node);
            }
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        return list;
    }
}

思路为找到所有的具有子节点的节点，然后从后往前进行遍历查找。对于每个父节点而言，我们可以进行先序遍历，然后判断是否o1和o2的值同时存在即可，如果同时存在，那么直接返回该节点的值即可。
涉及知识点，层序遍历。