Lowest Common Ancestor (1) 썸네일형 리스트형 167. Lowest Common Ancestor 다음과 같은 트리가 있다고 가정해 보자.$9$번 정점이 루트라고 하면 다른 정점들의 부모와 조상들을 결정할 수 있다. 예를 들어 $3$번 정점의 부모는 $9$번 정점이고, $8$번 정점의 조상은 $5$번 정점과 $9$번 정점이 된다. 이제 여러 정점의 조상을 생각해 보자. $7$번 정점의 조상은 $4$번, $3$번, $9$번 정점이고 $6$번 정점의 조상은 $3$번, $9$번 정점이다. 여기서 $3$번과 $9$번 정점은 $6$번 정점의 조상이면서 $7$번 정점의 조상이다. 이런 정점들을 $7$번 정점과 $6$번 정점의 공통 조상(Common Ancestor)이라고 한다. 또한 이중 깊이가 가장 깊은 정점은 $3$번 정점인데, 이 정점을 $7$번 정점과 $6$번 정점의 최소 공통 조상(Lowest Comm.. 이전 1 다음
