倍增(lcm+java)

时间：2021-03-07 21:52:56 收藏：0 阅读：30

问题：求一个二叉树，x节点到y节点的距离

算法：找到xy最近的父节点，res=cent[x]+cent[y]-2*cent[lcm(x,y)]

class Node{
	int l;
	int r;
	int cent;
	int father;
}


static int lcm(int u,int v) {
        while(u!=v) {
            if(node[u].cent>node[v].cent)u=node[u].father;
            else if(node[u].cent<node[v].cent)v=node[v].father;
            else {
                u=node[u].father;
                v=node[v].father;
            }
        }
        return u;
    }

原文：https://www.cnblogs.com/ydcwp/p/14496465.html