seogudwns12   1년 전

전위순회에 차례대로 50 31 30 24 5 28 45 98 52 60 이 들어갔을 때

후위순회에는 2가지 케이스가 가능한데 차례대로

1. 5 28 24 45 30 31 60 52 98 50 (45가 30의 child인 경우.)

2. 5 28 24 30 45 31 60 52 98 50 (45가 31의 child인 경우)

입니다.

물론 푼 사람이 있으니 채점케이스에 대해서는 이런 반례가 없을 것 같기는 하지만 문제 설명의 고려사항에 들어갈 필요는 있을 것 같습니다. 

위 예시의 그림파일 첨부합니다.(막그려서 숫자가 좀 개판입니다..)

preview

f52985   1년 전

아니요, 답은 언제나 유일합니다.

제시해주신 예제에서, 45가 30의 자식인 경우는, 이진 검색 트리의 정의에 부합하지 않습니다.

f52985   1년 전

45라는 노드가 31이라는 노드의 왼쪽 서브트리에 존재함에도 불구하고, 45가 31보다 크기 때문이죠.

seogudwns12   1년 전

아하.. 제가 문제를 잘못 읽었던 것이었네요..!.. 감사합니다!!!

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