POV

지침

선택한 노드를 기준으로 트리의 부모 관계를 다시 설정해요.

트리는 모든 노드가 연결되어 있지만 순환이 없는 특별한 종류의 그래프예요. 즉, 어떤 두 노드를 골라도 한 노드에서 다른 노드로 가는 경로가 정확히 하나만 있어요.

이 연습 문제는 트리를 다른 관점에서 바라보도록 방향을 바꾸는 것에 관한 거예요. 예를 들어 가계도는 보통 조상의 관점에서 표현해요:

    +------0------+
    |      |      |
  +-1-+  +-2-+  +-3-+
  |   |  |   |  |   |
  4   5  6   7  8   9

하지만 트리에는 원래부터 정해진 방향이라는 게 없어요. 같은 정보를 트리의 다른 어떤 노드의 관점에서도 표현할 수 있어요. 그 노드를 루트로 끌어올리고 그 관계들도 함께 끌고 가면 돼요. 그래서 같은 트리를 6의 관점에서 보면 이렇게 돼요:

        6
        |
  +-----2-----+
  |           |
  7     +-----0-----+
        |           |
      +-1-+       +-3-+
      |   |       |   |
      4   5       8   9

이렇게 하면 두 노드 사이의 경로를 더 간단하게 설명할 수 있어요. 예를 들어 6-9 경로는 (첫 번째 트리에서는 루트까지 올라갔다가 다른 리프 노드로 내려가죠) 6-2-0-3-9 경로를 따라간다는 걸 알 수 있어요.

이 연습 문제에서는 입력으로 주어진 트리를 노드 하나의 관점에서 다시 방향을 바꿔요.

Rust 관련 연습 문제 참고 사항

트리를 내부적으로 어떻게 표현할지는 자유롭게 정해도 돼요. 다만 자식들을 순서가 있는 컨테이너에 저장한다면 주의해야 해요. 두 트리는 자식들의 순서와 상관없이 서로 같다고 비교되어야 해요.

---

출처

4clojure의 연습 문제를 각색한 것이에요.