LCA

Lowest Common Ancestor로, 트리의 깊이를 모두 안다는 전제 하에 가장 가까운 공통 조상을 찾는 알고리즘이다

1. 두 트리의 깊이가 같아질 때까지, 두 트리 중 보다 깊은 트리를 올린다

2. 같은 노드가 나올 때까지 한 칸씩 올린다  

 

이를 이용해서, 두 트리의 거리도 알 수 있다. LCA로 조상을 찾고, 두 트리의 조상까지의 거리를 더하면 그 것이 정점의 거리가 된다