25207번 - 바벨탑의 저주
틀렸습니다 뜹니다.
분명 증명이 틀린거 같습니다.
1. 트리를 시리얼로 변환을 할 때
부모를 앞에 서브트리를 바로 뒤에 쓰는 방식 (깊이를 같이 기록) 으로 시리얼로 나타내면
시리얼에서 같은 깊이 숫자 사이의 시리얼은 서브트리를 나타내므로
(예: ...1232331... 의 시리얼은 아래와 같은 서브트리를 포함합니다.
o
| |
o o
| | |
o o o
)
유일하게 트리를 나타낼 수 있지 않나요?
2. 그리고 각 서브트리를 왼쪽 부터 시리얼로 변환한 것과 오른쪽 부터 시리얼로 변환한 것은 서브트리를 뒤집은 것과 동치 아닌가요?
어디서 오류가 있는걸까요?
안녕하세요, 멋진 풀이 감사합니다! 한 부모 노드에게 자식 노드가 여럿이라면 노드 번호가 더 작은 자식이 왼쪽에 있습니다. 따라서 다음과 같은 입력에서 저주 노드는 루트를 포함한 5개입니다. 이 부분만 고치시면 맞을 것 같습니다.
긴 코드 보고 반례 까지 적어주시다니 정말 감사합니다.
트리 정렬하고 바로 맞았습니다 ㅎㅎ.
댓글을 작성하려면 로그인해야 합니다.
akswnd98 1년 전
틀렸습니다 뜹니다.
분명 증명이 틀린거 같습니다.
1. 트리를 시리얼로 변환을 할 때
부모를 앞에 서브트리를 바로 뒤에 쓰는 방식 (깊이를 같이 기록) 으로 시리얼로 나타내면
시리얼에서 같은 깊이 숫자 사이의 시리얼은 서브트리를 나타내므로
(예: ...1232331... 의 시리얼은 아래와 같은 서브트리를 포함합니다.
o
| |
o o
| | |
o o o
)
유일하게 트리를 나타낼 수 있지 않나요?
2. 그리고 각 서브트리를 왼쪽 부터 시리얼로 변환한 것과 오른쪽 부터 시리얼로 변환한 것은 서브트리를 뒤집은 것과 동치 아닌가요?
어디서 오류가 있는걸까요?