최소 공통 조상(Lowest Common Ancestor)

개념요약

• 트리상에서 임의의 두 정점이 있을때 두 정점의 부모노드를 타고 갔을때, 겹치면서 가장 깊은 노드이다.
• 푸른색이 두 정점, 붉은색이 LCA이다.

풀이 방식

1. 모든 노드에 대한 깊이를 계산한다.
2. 최소 공통 조상을 찾을 두 노드를 확인한다.
3. 두 노드의 깊이가 동일할 때까지 거슬러 올라간다.
4. 부모가 같아질 때까지 두 노드의 부모로 거슬러 올라간다.

 

코드

Node	&LCA(Node lhs, Node rhs)
{
	while(true)
	{
		if (lhs.depth == rhs.depth)
		{
			if (lhs.parent == rhs.parent)
				return (lhs.parent);
			else
			{
				lhs = lhs.parent;
				rhs = rhs.parent;
			}
		}
		else if (lhs.depth > rhs.depth)
			lhs = lhs.parent;
        else if (lhs.depth < rhs.depth)
			rhs = rhs.parent;
	}
}