akswnd98   1년 전

틀렸습니다 뜹니다.

분명 증명이 틀린거 같습니다.

1. 트리를 시리얼로 변환을 할 때

부모를 앞에 서브트리를 바로 뒤에 쓰는 방식 (깊이를 같이 기록) 으로 시리얼로 나타내면

시리얼에서 같은 깊이 숫자 사이의 시리얼은 서브트리를 나타내므로

(예: ...1232331... 의 시리얼은 아래와 같은 서브트리를 포함합니다.

                o

             |    |

             o      o

          |       |   |

          o       o   o

)

유일하게 트리를 나타낼 수 있지 않나요?

2. 그리고 각 서브트리를 왼쪽 부터 시리얼로 변환한 것과 오른쪽 부터 시리얼로 변환한 것은 서브트리를 뒤집은 것과 동치 아닌가요?

어디서 오류가 있는걸까요?

yooshnn   1년 전

안녕하세요, 멋진 풀이 감사합니다! 한 부모 노드에게 자식 노드가 여럿이라면 노드 번호가 더 작은 자식이 왼쪽에 있습니다. 따라서 다음과 같은 입력에서 저주 노드는 루트를 포함한 5개입니다. 이 부분만 고치시면 맞을 것 같습니다.

akswnd98   1년 전


긴 코드 보고 반례 까지 적어주시다니 정말 감사합니다.

트리 정렬하고 바로 맞았습니다 ㅎㅎ.

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