lca问题

lca问题即求解一棵树中给定的两个结点的最深公共祖先问题。

　　对于给定了前序遍历和中序遍历的树，参考pat1151

void lca(int inl,int inr,int preRoot,int a,int b){
    if(inl>inr)
        return;
    int inRoot=all[pre[preRoot]];
    int ina=all[a];
    int inb=all[b];
    if(ina<inRoot&&inb<inRoot)
        lca(inl,inRoot-1,preRoot+1,a,b);
    else if((ina<inRoot&&inb>inRoot)||(ina>inRoot&&inb<inRoot))
        printf("LCA of %d and %d is %d.
",a,b,pre[preRoot]);
    else if(ina>inRoot&&inb>inRoot)
        lca(inRoot+1,inr,preRoot+1+inRoot-inl,a,b);
    else if(ina==inRoot){
        printf("%d is an ancestor of %d.
",a,b);
    }
    else if(inb==inRoot)
        printf("%d is an ancestor of %d.
",b,a);
}

首先需要判断下结点是否存在，然后调用上述lca算法，其中a,b表示待查找的结点，inl和inr表示中序遍历的左右边界。all是一个map,记录结点i在中序遍历中的位置，preRoot表示当前子树中根节点在前序遍历中的位置。

　　对于二叉查找树的lca问题，参考pat1143

更一般的算法是

1.Tarjan（离线）算法

2.倍增算法

3.RMQ算法

这三个先留个坑，后面补