BOJ 2250 트리의 높이와 너비

이진트리가 주어지면 문제에 주어진 규칙에 따라 각 레벨의 너비 중에서 가장 넓은 너비를 구하는 문제인데, 각 레벨의 왼쪽 끝 노드와 오른쪽 끝 노드 사이의 너비를 구하는 것인데... 그 사이의 공간은 트리에서 나머지 노드들이 빈틈없이 하나씩 차지하고 있다.

잘 생각해보면 각 노드에 왼쪽부터 시작해서 레벨 상관없이 왼쪽에서 몇 번째에 위치하는지 번호를 매겨놓으면 쉽게 풀 수 있을 것 같다. 어떻게 왼쪽부터 번호를 매길까? 바로 left subtree -> root -> right subtree순으로 탐색하는 inorder traversal를 이용하면 된다.

그럼 inorder traversal로 번호를 매기고, 탐색하면서 각 레벨별로 최소, 최대값을 찾으면 너비를 구할 수 있을 것이다.

그리고 문제에 딱히 루트가 몇 번 노드인지 안 나와있으므로 알아서 루트를 찾아야할 것 같다. 루트는 부모노드가 없는 노드이므로 입력에서 자식 노드로 언급이 되지 않은 노드를 루트로 놓으면 될 것 같다.

제출했는데 틀려서 원인을 살펴보니.. inorder traversal을 하면서 level도 같이 계산해주는데, lvl 변수를 parameter로 보내면서 ++lvl을 해줬는데, left subtree나 right subtree가 없는 경우(-1)에는 ++lvl이 안되는 문제가 있었다. 그래서 parameter위치에서 하지말고 미리 ++lvl을 해주고 parameter로 넘기는 것으로 해결했다.

그런데도 또 틀려서 n이 1일 때를 해봤는데, 오답이 나온다. 개선해 봐야겠다.
예제를
1
1 -1 -1
이것으로 해봤는데, 정말 감사합니다. 이 예제가 아니었으면 찾기 힘들었을 것 같다.
원인은 답을 구할 때, max - min +1이 너비의 답인데, ans의 너비 최대값을 갱신하기 위해 ans<max-min 인 경우 ans=max-min+1을 해주고 있었다... ans<max-min+1인 경우로 해야하는데... 엄청나게 허무한 실수이면서 찾기 힘든 실수였다.
결국 AC를 받았다.

아이디어는 비교적 빨리 떠올랐고 집중했는데도 불구하고 1시간 반정도가 걸린 것 같다...그리고 좋은 문제 같다.