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

先序遍历深度优先搜索树，分别找到根节点到o1和o2的路径，对比路径中第一个不相同的点，即为最近的公共祖先

static int opath[100000],opath1[100000],opath2[100000],top=0;
int findpath(struct TreeNode* pRoot,int o1,int o2){
    if(pRoot==NULL)
        return 0;
    opath[top++]=pRoot->val;
    if(pRoot->val==o1){
        for(int i=0;i<top;i++)
            opath1[i]=opath[i];
    }
    if(pRoot->val==o2){
        for(int i=0;i<top;i++)
            opath2[i]=opath[i];
    }
   
       
    findpath(pRoot->left,o1,o2);
    findpath(pRoot->right,o1,o2);
    //这里迭代，返回上层
    top--;
    return 0;
}
int lowestCommonAncestor(struct TreeNode* root, int o1, int o2 ) {
    findpath(root,o1,o2);
    int i=0;
    while(opath1[i]==opath2[i])
        i++;
    return opath1[i-1];
}