티스토리 뷰
4256번: 트리
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음
www.acmicpc.net
1. Preorder는 루트, 왼쪽, 오른쪽 순으로 방문하므로 제일 먼저 출력하는 정점은 항상 탐색하려는 트리의 루트이다.
2. Inorder는 왼쪽, 루트, 오른쪽 순으로 방문하므로 루트를 기준으로 왼쪽에 있는 정점들은 루트의 왼쪽 서브 트리, 오른쪽에 있는 정점들은 루트의 오른쪽 서브 트리를 구성하는 정점들이다.
3. 위 성질을 이용하여, Preorder의 탐색 순서에 맞추어 Inorder 내의 정점들을 잘 잘라나가면 원래의 트리를 구할 수 있다.
- Source code link
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- boj 2336
- 백준 2243
- 백준 1106
- 백준 3006
- boj 10775
- 터보소트
- 백준 10775
- boj 1106
- 백준 10473
- boj 10473
- 백준 12713
- boj 3006
- boj 1280
- boj 9345
- boj 12713
- boj 2243
- boj 14868
- Ugly Numbers
- 백준 16562
- 백준 9345
- 제로베이스 백엔드 스쿨
- 백준 2336
- boj 16562
- 제로베이스 스쿨
- 디지털 비디오 디스크
- 백준 14868
- 인간 대포
- 부트 캠프
- 백준 1280
- 사탕상자
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 | 31 |
글 보관함