/**

  • 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* find(TreeNode* root,int o1,int o2)//函数原型没问题吧，返回的是自定义类型指针
{
    if(root==NULL||root->val==o1||root->val==o2)//base case
        return root;
    //哇，这个base case啥意思啊，没啥意思字面意思，如果当前指针的值是这三个其中之一就返回
    //下面还会对这个if语句剖析，你就照我说的先理解着
    else
    {
        TreeNode* leftData,*rightData;//这两干嘛的呢，存储我左右子树返回上来的信息
        leftData=find(root->left, o1,  o2);//存储左子树给我反馈上来的信息
        rightData=find(root->right,o1,o2);//存储我右子树反馈上来的信息,可能已经有点懵了，没关系
        //下面最难理解的部分来了
        if(leftData!=NULL&&rightData!=NULL)
            return root;
        //我们来着重分析上面这条if语句，心理想着最下面分析的两种情况，发现没，其实这条if语句
        //说的就是第一种情况，为什么？看最上面那条if语句，我当前节点的左子树给我的信息不为空而且右子树给我的信息也不为空
        //这不就恰恰说明o1,o2位于当前这个节点的左右两颗子树上吗？那当前这个节点不就是最近的公共祖先吗?看不懂可以画个树看看
        //所以我直接return 当前root不就行了吗。
        else{
            return leftData==NULL?rightData:leftData;//这个else就代表最下面分析里的第二种情况
            //什么意思呢？第二种情况是不是说明o1,o2有一个在上面对吧，那我们画图可以看出，此时o1，o2的最近公共祖先
            //是不是一定是物理位置在上面的那个对吧。我们再看最上面那条if语句，我遇到o1，或者o2就是return
            //是不是正好是正确答案？所以第二种情况下说左右子树只有一个不空，我返回那个不空的就行了
        }
    }
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
    // write code here
    //这题就很恶心了，恶心就恶心在要求空间复杂度为O（1），本来我一看找最近祖先
    //用哈希表存父亲路径不就完了吗，现在不能这样做了，那怎么做呢？ai，自有办法
    //这个方法对于像我这样的新手还是很不友好的，当初也是看了挺久的，分享给大家，我尽力讲的通俗点，最下面是分析
    //在主方法里调用递归函数得到最近公共祖先的节点指针
    TreeNode* p=find(root, o1, o2);
    return p->val;
    //我这么用心，才不是想要你的赞呢（傲娇~）
}

}; /* 在写之前呢有些东西大家必须要想清楚 两个节点在一棵二叉树上的分布总的来说有几种呢？答：就两种 第一种是：o1,o2分别位于两个字树上没上下物理位置上的关系 第二种是：o1,o2位于一颗树上,在物理位置上可能o1在o2上面，也可能呢o2在o1上面，这两种情况无所谓重点是他两有物理上的上下关系即在同一棵子树上 请大家牢记这两种情况下面我们看代码，代码和这两个前提牢牢相关 */