二叉树的最近公共祖先

若root是p,q的最近公共祖先,则只可能为以下情况之一：

1. p和q在root的子树中，且分列root的异侧（即分别在左、右子树中）；
2. p=root,且q在root的左或右子树中；
3. q=root，且p在root的左或右子树中；

   /**
   * struct TreeNode {
   *    int val;
   *    struct TreeNode *left;
   *    struct TreeNode *right;
   * };
   */
   class Solution {
   public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    TreeNode *ret;
    bool dfs(TreeNode *root,int o1,int o2)
    {
        if(!root)
            return false;
        bool l=dfs(root->left,o1,o2);
        bool r=dfs(root->right,o1,o2);
        if((l&&r)||((root->val==o1||root->val==o2)&&(l||r)))
   //判断root是否包含o1和o2或root值为o1或o2且o2或o1出现在root子树中
        {
            ret=root;
        }
        return l||r||root->val==o1||root->val==o2;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        dfs(root,o1,o2);
            return ret->val;
    }
   };