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

1. 如果该节点不是O1也不是O2，那么O1与O2必然分别在该节点的左子树和右子树中
2. 如果该节点就是O1或者O2，那么另一个节点在它的左子树或右子树中 稍微可以优化的一点就是，遇到O1或者O2节点就不往下递归了，把O1或者O2节点一层层往上传

/*
 * 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
        TreeNode res=dfs(root,o1,o2);
        return res.val;
        
    }
    
    TreeNode dfs(TreeNode root,int p,int q){
        if(root==null||root.val==p||root.val==q) return root;
        TreeNode left=dfs(root.left,p,q);
        TreeNode right=dfs(root.right,p,q);
        
        return left==null?right:(right==null?left:root);
    }
}