5639번 - 이진 검색 트리
전위순회에 차례대로 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인 경우)
입니다.
물론 푼 사람이 있으니 채점케이스에 대해서는 이런 반례가 없을 것 같기는 하지만 문제 설명의 고려사항에 들어갈 필요는 있을 것 같습니다.
위 예시의 그림파일 첨부합니다.(막그려서 숫자가 좀 개판입니다..)
아니요, 답은 언제나 유일합니다.
제시해주신 예제에서, 45가 30의 자식인 경우는, 이진 검색 트리의 정의에 부합하지 않습니다.
45라는 노드가 31이라는 노드의 왼쪽 서브트리에 존재함에도 불구하고, 45가 31보다 크기 때문이죠.
아하.. 제가 문제를 잘못 읽었던 것이었네요..!.. 감사합니다!!!
댓글을 작성하려면 로그인해야 합니다.
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인 경우)
입니다.
물론 푼 사람이 있으니 채점케이스에 대해서는 이런 반례가 없을 것 같기는 하지만 문제 설명의 고려사항에 들어갈 필요는 있을 것 같습니다.
위 예시의 그림파일 첨부합니다.(막그려서 숫자가 좀 개판입니다..)