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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
                            //本题解法好像不满足时间复杂度On，已经要达到1秒了
    int num=0;              //用于控制存入双亲表示法的结构体的变量

    typedef struct tree{
        int val;
        int parent;
    }tree;               //树的双亲表示法的结构体

    tree a[100000];     //结构体声明

    void jianli(TreeNode* root,int b){     //该方法将链式存储改为顺序双亲存储
        a[num].val=root->val;
        a[num].parent=b;
        b=num;
        num++;
        if(root->left!=NULL) jianli(root->left,b);
        if(root->right!=NULL) jianli(root->right,b);
    }

    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        for(int i=0;i<100000;i++) a[i].val=-1,a[i].parent=-2;  //初始化
        jianli(root,-1);      //建立
        int j,k;
        for(int i=0;i<100000;i++){      //找到目的节点的位置
            if(a[i].val==o1) j=i;
            if(a[i].val==o2) k=i;
        }
        int e[100000],g=0,h=0;
        while(j!=-1){            //将其中一个节点的所有双亲列出
            e[g]=a[j].val;
            j=a[j].parent;
            g++;
        }
        while(k!=-1){           //另一个节点的每个双亲跟前一个结点的双亲去匹配，第一个相同的就是结果
            for(int i=0;i<100000;i++){
                if(a[k].val==e[i]){
                    h=e[i];
                    break;
                }
            }
            k=a[k].parent;
            if(h!=0) break;
        }
        return h;
    }
};