khiros   10달 전

 이진트리의 중위&후위순회 결과를 받아 전위순회를 반환하는 2263번 트리의 순회 문제에 대한 요청입니다.

 현재 아래와 같이 후위순회의 결과로 root를 찾고, 그 root를 중위순회에서 찾아 분할정복을 하는 과정으로 문제를 해결하였고, 문제에서 "맞았습니다"를 받았습니다.

 하지만 path처럼 왼쪽/오른쪽 자식중 하나만 있는 경우에는 분할이 균등하게 이루어지지 않아, O(N log N)의 시간복잡도를 장담하지 못하고, 최악의 경우에는 O(N^2)까지 시간복잡도가 증가합니다. 아래 코드의 경우 모두 왼쪽 자식만 있는 경우에 O(N^2)의 시간복잡도를 받습니다. 

N<=100'000의 조건에서 맞는 것을 보아 이와 같은 테스트케이스가 없는 것 같습니다. 이와 같은 테스트케이스를 추가해주시거나, 문제 설명에 이진트리가 아니라 완전이진트리 등으로 명시해 O(N log N)의 시간복잡도를 보장해주시면 좋겠습니다.

댓글을 작성하려면 로그인해야 합니다.