추가 저장소와 별도의 이진 검색 트리에서 k 번째로 큰 경로 합계 찾기

Question

배열과 같은 다른 저장소를 사용하지 않고 이진 검색 트리에서 가능한 전체 전체 경로 합계 중 최대 k 번째 항목을 찾을 수있는 방법이 있습니까? 처음에는 포인터를 늘리는 동안 오른쪽에서 합계를 찾는다면 각 새 합계가 최소값이되고 이전 합계 (처음에는 합계가 무한 값)가되고 k에 도달하면 끊어지는 것으로 생각했습니다. 그러나 나는 방금 최대 리프 값이 자연스럽게 오른쪽에서 왼쪽으로 정렬되지만 합계는 그렇게 필요하지 않음을 발견했습니다. 따라서이 방법은 효과가 없습니다. 어떻게해야합니까?

Answer 1

k-smallest를 계산할 수 있다면 동일한 알고리즘으로 k-largest를 계산할 수 있습니다. 왼쪽에서 오른쪽으로 이동하는 대신 오른쪽에서 왼쪽으로 작업을 수행하면됩니다.