KEEP GOING

문제를 풀기 위해 앞서 알아야 할 지식은 최소 공통 조상을 찾는 LCA에 대한 개념이다. * LCA(Lowest Common Ancestor) 트리 내에서 공통 부모인 LCA를 찾아주는 알고리즘 두 점 사이의 거리를 구할 때 사용한다. ( 두 노드의 공통된 조상 중에서 가장 가까운 조상 찾기 ) 처음 트리 생성 시 각 노드마다 부모 노드와 level을 정리한다. 두 노드에서 올라가면서 부모 노드가 같아질 때까지 찾아간다. * A와 B 두 점 사이의 거리 = 1부터 A까지의 거리 + 1부터 B까지의 거리 - 1부터 LCA까지의 거리*2 예를 들어, 아래와 같이 이진 트리가 주어진 경우 12번 노드와 7번 노드의 거리 = 1부터 12까지의 거리 + 1부터 7까지의 거리 - 1부터 LCA(3)까지의 거리*2 ..