위성

지침

대역폭이 제한된 상황에서 알파 센타우리로 다가가는 인공위성에 이진 트리를 전송해야 한다고 상상해 봐요. 트리에는 중복되는 항목이 없기 때문에, 전위 순회와 중위 순회 결과만으로 트리를 유일하게 표현할 수 있어요.

순회 결과로부터 트리를 복원하는 소프트웨어를 위성용으로 작성해 봐요.

전위 순회는 왼쪽 서브트리를 전위 순회로 읽기 전에(그래서 "전위"예요) 현재 노드의 값을 읽어요. 그다음 오른쪽 서브트리를 전위 순회로 읽어요.

중위 순회는 왼쪽 서브트리를 중위 순회로 읽고, 그다음 현재 노드를, 마지막으로 오른쪽 서브트리를 중위 순회로 읽어요. 즉 왼쪽에서 오른쪽 순서예요.

예를 들어 이 트리의 전위 순회는 [a, i, x, f, r]이고, 중위 순회는 [i, a, f, x, r]예요.

  a
 / \
i   x
   / \
  f   r

참고: 전위 순회의 첫 번째 항목은 항상 루트예요.

예외 메시지

때로는 예외를 발생시켜야 할 때도 있어요. 이때는 오류의 원인이 무엇인지 알려 주는 의미 있는 오류 메시지를 항상 포함해야 해요. 그러면 코드를 더 읽기 쉽게 만들고, 디버깅에도 큰 도움이 돼요. 오류의 원인이 특정 유형이라고 확실한 상황이라면 내장 오류 유형 중 하나를 골라 발생시켜도 되지만, 그래도 의미 있는 메시지는 포함해야 해요.

이 연습 문제에서는 preorder와 inorder 인자가 길이나 원소가 서로 맞지 않거나, 원소가 중복되는 경우 raise 문을 사용해 ValueError를 "던져야" 해요. 테스트는 exception을 raise하고 메시지도 함께 넣을 때만 통과해요.

메시지와 함께 ValueError를 발생시키려면, 메시지를 exception 타입의 인자로 작성해요:

# if preorder and inorder are not the same length
raise ValueError("traversals must have the same length")

# if preorder and inorder do not share the same elements
raise ValueError("traversals must have the same elements")
    
# if element repeat (are not unique)    
raise ValueError("traversals must contain unique items")