jjh4698   7년 전

start가 중위순회의 시작점, 중위순회의 마지막점을 기준으로


후위 순회를 통해서 루트를 찾고,

루트의 왼쪽을 서브트리로 재귀 돌리고

루트의 오른쪽을 서브트리로 재귀 돌렸는데

O(NlogN+N) 으로 구현한거 같은데 문제가 있나요?

xkdlaldfjtnl   3년 전

너무 오래된 글이지만 댓글 남깁니다. 

int find_root(int start, int end)
{
int ret = 0;
for (int i = start; i <= end; i++)
ret = max(ret, last_index[middle[i]]);
return ret;
}

만약에 한 노드에 하나의 자식만 있고, 그 자식이 우측에만 있으면 (n-1+n-2+n-3+...+1)해서 n(n+1)/2 이것떄문에 시간초과가 나지 않았을까 생각합니다.  

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