！！！题解 | 在二叉树中找到两个节点的最近公共祖先 主要是列举各种情况然后再整合

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        //可以使用递归的方法来做。其实主要还是分析各种情况。第一种情况在左边找这两个节点、在右边找这两个节点，如果左右都能找到，那么说明当前节点就是根节点。第2种情况，只在左边找到了，右边没找到那么，在左边最开始找到的那个节点就是目标节点。第3种情况，就是和这个对称。第4种情况就是左右两边都没有找到，但当前节点是这二者其中之一的话，就可以向上回溯了；但是需要记录这个结点信息，因为如果它们在同一棵子树上，那么这一点就是祖先节点，所以可以直接返回；如果在右子树上找到了另一个节点的信息那么就是第一种情况。
        TreeNode* ob=getancester(root, o1, o2);
        if(ob)return ob->val;
        else return -1;
    }
    
    TreeNode* getancester(TreeNode* root,int o1,int o2){
        if(root==nullptr||root->val==o1||root->val==o2)return root;
        TreeNode* left=getancester(root->left,o1,o2);
        TreeNode* right=getancester(root->right,o1,o2);
        if(left&&right)return root;
        else if(left&&!right)return left;
        else if(right&&!left)return right;
        else return nullptr;;
    }
};