트리 관련 문제 솔루션

[1. 개요]

Tree 자료 구조의 특징

• 하나의 노드는 여러개의 자식을 가질 수 있어도, 부모는 하나만 가질 수 있다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.
  => 부모가 반드시 하나만 있다는 점을 생각해보자.
  => leaf 에서 위로 올라가는 경로는 유일하다.
• Root 는 트리에서 딱 하나 존재한다.
• Leaf 는 자식이 없는 노드이다.
• Cycle 이 존재하지 않는 연결그래프 (무방향) 이다.
  => 어떤 그래프에서 DFS 를 한번 수행하면, DFS 스패닝 트리가 된다.
  => 어떤 그래프에서 BFS 를 한번 수행하면, 역시 트리가 된다.
  => 이러한 점을 고려하도록 한다.
• Tree 의 지름
• 재귀적인 성질을 갖는다.
  => 재귀적인 방식으로 코드를 작성해야 하는 이유이다.
  => 전위, 중위, 후위 순회...
• 트리인 경우, 정점이 n개 이고, 간선이 (n-1)개 있어야 한다.
  => 역은 보통 성립하지 않는다.
• 그리고 또...

자료구조 구현 패턴

• parents[root] = root 
  => 부모가 자기 자신인 경우 => root node

재귀함수 구현 패턴

• DFS,  방문여부를 체크해도 되지만,
• 트리 형태이므로, 인접한 노드가 부모인지 아닌지만 체크해도 된다.

동적 계획법

• 간혹 DP 가 필요 한 경우가 있다.
• 이 경우, 반복적 동적계획법 형태로 접근하는 것이 좋아 보인다.
• 가장 적합한 탐색을 DFS, 재귀로 구현하므로,

기타 팁

• 트리의 root 는 임의의 노드로 선정해도 된다. (보통 1 과 같이, 가장 빠른 node id)

---

[2. 예제]

• https://testkernelv2.tistory.com/470
• https://testkernelv2.tistory.com/547
• https://testkernelv2.tistory.com/548
• https://testkernelv2.tistory.com/550
• e
• f
•