최근에 프로그래밍 문제가 발생했습니다.트리에서 노드 집합 사이의 최장 경로 찾기
주어진 트리는 N이 아닌 바이너리 일 수 있으며, N 개의 노드가있는 단일 체인 (또는 선형)이 될 수 있습니다.
입력은 a1, a2 .... ak로 표시된 K 노드 세트입니다. 그 중 하나의 K 노드에서 시작하여 K 노드 중 하나 (시작 노드와 다름)에서 끝나는 가장 긴 단순 경로를 찾고 싶습니다. N 또는 K에 따른 로그 알고리즘이 필요한 시간 제한 내에 있어야하는 경우 실행 시간 요구 사항 (예 : KlogK, KlogN)을 충족해야합니다.
당신이
어쩌면 당신은이 방법을 시도 할 수 있습니다 감사 - 가장 먼 리프 노드를 찾기 위해 모든 노드에서
이것은 이진 트리가 아닌 모든 트리에서 작동합니다.
이라는 말을 고쳤다. 정교하기 위해, 여기에 언급 된 알고리즘은 모든 트리에서 가장 긴 단순 경로를 찾습니다. 그래서 당신의 경우, 주어진 k 노드의 '아래'에있는 트리의 모든 부분을 잘라 내야합니다. 그러니 먼저 나무로 시작하여'ai' 세트가 아닌 나뭇잎을 제거하십시오. 이 시점에서 모든 나뭇잎은 주어진 세트에 있습니다. 그런 다음 위의 3 단계를 실행하십시오. – Samee
잎을 제거하는 것은 O (n)를 가지고 간다 그러나 최악의 경우에 잎은 제거되지 않을 것이다. 2 DFS는 각각 O (n)을 필요로하며, O (3n)은 너무 느립니다. – user2129227
모든 노드에 충돌해야합니까? 노드를 다시 방문 할 수 있습니까? –
아니요, 해당 K 노드에서만 시작하고 완료하십시오. 단순 경로, 노드를 다시 방문 할 수 없습니다. 나는 – user2129227