챕터7-3. 트리 | 문제풀이
개념을 적용한 문제풀이
# 이진트리의 프리오더, 인오더, 포스트오더 순서를 출력하는 문제
- https://www.acmicpc.net/problem/1991
- 코드상에서 3가지 방법의 차이는 출력을 언제 하는가의 차이이다.
- 알파벳을 숫자화 해서 A : 0, B : 1, C : 2, ... i의 값으로 사용하고,
2차원 배열로 A[i][0] = 왼쪽 자식 값, A[i][1] = 오른쪽 자식 값을 저장하는 방식으로 트리를 저장하였음.
자식이 없는 경우 -1을 넣어주어 재귀호출이 끝나도록 하였음.
* 이진트리의 순회는 왼쪽 자식과 오른쪽 자식의 값을 구분해 가지고 있는게 출력하기 편함.
# 트리의 부모 찾기
- https://www.acmicpc.net/problem/11725
- DFS, BFS 두 방법 모두 사용이 가능한 해결방법이다.
그 이유는 루트부터 모든 노드를 한번씩 방문하는 과정 중에 이는 간선이 있고 아직 방문하지 않은 경우에만 가능하기 때문에
A->B가 이뤄진 경우 A는 B의 부모라고 할 수 있다.
- 이 문제를 응용하면 각 노드의 depth를 구할 수도 있다.
depth를 구하고 싶으면 parent 값을 넣어주는 부분을 다음과 같이 처리하면 된다. depth[y] = depth[x] + 1
# 트리의 지름
- https://www.acmicpc.net/problem/1167
- 트리의 지름 : 존재하는 모든 경로 중에서 가장 긴 것의 길이
- 문제에서 거리라고 하는 것은 가중치를 의미한다.
- 트리의 지름은 2번의 탐색을 통해 구할 수 있다.(알고리즘임)
1) 임의의 정점을 루트로 설정한뒤, 루트에서 모든 정점까지의 거리를 구한다. 이때, 가장 먼 거리였던 정점을 A라고 한다.
2) A를 루트라고 하고 모든 정점까지의 거리를 구한다. 이 때 구한 가장 먼 거리가 지름이다.
