제가 생각한 알고리즘이 어차피 가장 먼 거리가 될려면 두 단말노드 사이의 거리가 될 거고, 그러면 그 두 단말 노드의 공통조상이 root라고 할 때, 그 root에서부터 단말노드까지의 경로들 중 가장 깊이가 깊은 두개의 경로의 합이 거리가 된다고 생각하고(대신 그 두 단말노드의 최저 공통 조상은 root가 되야 하겠죠) 알고리즘을 짰는데... 왜 틀렸을까요 ㅠㅠ 혹시 단말노드 두개의 최저 공통조상이 root가 안되는건가요? 사이클이 안생겨야 되니까 그럴거같지는 않은데...
wwiiiii 9년 전 2
제가 생각한 알고리즘이 어차피 가장 먼 거리가 될려면 두 단말노드 사이의 거리가 될 거고, 그러면 그 두 단말 노드의 공통조상이 root라고 할 때, 그 root에서부터 단말노드까지의 경로들 중 가장 깊이가 깊은 두개의 경로의 합이 거리가 된다고 생각하고(대신 그 두 단말노드의 최저 공통 조상은 root가 되야 하겠죠) 알고리즘을 짰는데... 왜 틀렸을까요 ㅠㅠ 혹시 단말노드 두개의 최저 공통조상이 root가 안되는건가요? 사이클이 안생겨야 되니까 그럴거같지는 않은데...