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

递归遍历这棵树，如果在树的左右分别均找到了o1，o2，说明当前节点就是最近的公共祖先。

如果当前节点就是 o1，o2 中的值，且在左右子树中找到了一个，则说明，当前节点就是最近的公共祖先。

如果都不是，则返回当前子树中已经找到的节点。

import java.util.*;

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

public class Solution {
    private TreeNode traverse(TreeNode tree, int o1, int o2) {
        if (tree == null) {
            return null;
        }
        boolean found = false;
        if (tree.val == o1 || tree.val == o2) {
            found = true; 
        }
        TreeNode p1 = traverse(tree.left, o1, o2);
        TreeNode p2 = traverse(tree.right, o1, o2);
        if (p1 != null && p2 != null) {
            return tree;
        }
        if ((p1 != null || p2 != null) && found) {
            return tree;
        }
        if (found) {
            return tree;
        }
        return p1 != null?p1:p2;
    }
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return traverse(root, o1, o2).val;
    }
}