第二十七题  
两个方法
第一个是通过公共祖先之前的访问路径相同来找
第二个是构造完满二叉树 再用二叉树孩子p的父亲结点是p/2来暴力运算

方法1 找公共路径 匹配公共路径
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int findout=0;
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // 递归找到 从root到指定点的直接路径
        // 因为如果有公共结点 那么这个公共结点到root的路径应该是一样的
        // 所以，找到路径之后，再比对两者的公共路径 直到找到第一个不相同
        
        // write code here
        vector<int>o_1,o_2;
        findout=0;
        // 递归返回o_1 就是从root到o1经过的所有的点
        findpoint(o_1,root, o1);
        // 最后添加一个-1 表示结束了，处理边界问题
        // 用来解决 在最后一个o_1 o_2 较短的最后一个匹配了 的边界问题
        o_1.push_back(-1);
        // 递归调用获得o_2的路径
        findout=0;
        findpoint(o_2,root, o2);
        o_2.push_back(-1);
        
        // 输出o_1、o_2的代码
//         for(int i =0;i<o_1.size();i++)
//         {
//             cout<<o_1[i]<<" ";
//         }
//         cout<<endl;
//         for(int i =0;i<o_2.size();i++)
//         {
//             cout<<o_2[i]<<" ";
//         }
        
        // 因为如果有公共结点 那么这个公共结点到root的路径应该是一样的
        // 所以只要一个个往后比较 出现第一个不一样的时候，返回不一样的值的前一个。
        for(int i =0;i< min(o_1.size(), o_2.size());i++)
        {
            if(o_1[i] != o_2[i] )
                return o_1[i-1];
        }
        return -1;
    }
    
    // 找到到指定数字的路径
    void findpoint(vector<int> &ret_ans,TreeNode* root,int num)
    {
        if(root==NULL)
            return ;
        ret_ans.push_back(root->val);
        if(root->val == num)
        {
            findout=1;
            return;
        }
        // 递归找路径 
        // 如果说已经找到了 直接返回
        findpoint(ret_ans,root->left,num);
        if(findout==1)
            return;
        findpoint(ret_ans,root->right,num);
        if(findout==1)
            return;
        
        // 如果说不是该路径上的点 直接pop扔掉
        ret_ans.pop_back();
        return;
    }
        
};



方法2 与25题类似 暴力 构造成满二叉树 在按照满二叉树的性质 向上找结果
/**
 * 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 p int整型 
     * @param q int整型 
     * @return int整型
     */
    TreeNode* notnode=new TreeNode(-1);
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        // 知道深度 2^深度-1就是满二叉树的结点个数
        int depth = getdepth(root);
        
        // 保存层序遍历的结果
        int *cengxv=new int[int(pow(2,depth))];
        
        // 用于层次遍历 保存后续结点的队列
        queue<TreeNode *> que;
        // 第一次先把根节点放进去
        que.push(root);
        
        // 记录当前在第几层从1开始计算
        int level=1;
        
        // 层次遍历 如果队列不是空，则继续往下遍历
        // 从第一层开始  处理完深度的树
        while( level<=depth ){
            // length表示这一层存有几个 决定了之后要遍历的次数
            int length = que.size();
            int k=0;
            
            // 和之字形套路一样 只用队列中的length个
            while(length--)
            {
                // 如果说 这个点是我自己预留出来的空节点 也就是val=-1
                if(que.front()->val==-1){
                    que.pop();
                    // -1 表示为空 在找父节点的时候使用
                    cengxv[int(pow(2,level-1))+k] = '-1';
                    k++;
                    // 每一个空节点 会产生连个子空节点
                    que.push(notnode);
                    que.push(notnode);
                    continue;
                }
                
                // 访问当前结点
                TreeNode* thisnode = que.front();
                que.pop();
                
                // 把该节点的数据存到序列中
                // 每个点的位置是：2^(当前level) +k
                cengxv[int(pow(2,level-1))+k]=thisnode->val;
                k++;
                // 如果左右孩子还有 就push进队列（记住，此时所有入得队列 都代表是下一层的）
                // 反之，如果左右孩子是空 就push notnode （用来保证所传递的序列 位置上是有东西的）
                if(thisnode->left!=NULL)
                    que.push(thisnode->left);
                else
                    que.push(notnode);
                if(thisnode->right!=NULL)
                    que.push(thisnode->right);
                else
                    que.push(notnode);
            }
            
            // 到下一层处理
            level++;
        }
        
        int pp=-1,qq=-1;
        // 可以取消注释 看一眼所有保存到序列的值
        for (int i =1;i<int(pow(2,depth));i++){
            if(cengxv[i]==p)
                pp=i;
            if(cengxv[i]==q)
                qq=i;
//             cout<<cengxv[i]<<" ";
        }
        
        // p q 两个点的位置
        cout<< pp<<" "<<qq<<endl;
        while(pp!=qq)
        {
            if(pp > qq)
                pp=pp/2;
            else
                qq=qq/2;
        }
        
        return cengxv[pp];
    }
    
        // 知道深度 递归调用 就不说了
    int getdepth(TreeNode *root){
        int depth=0;
        if(root==NULL)
            return depth;
        int leftdepth=getdepth(root->left);
        int rightdepth = getdepth(root->right);
        depth = leftdepth > rightdepth ? leftdepth:rightdepth;
        return depth+1;
    }
};