티스토리 뷰
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
- 백준 14868
- 백준 9345
- boj 3006
- 제로베이스 백엔드 스쿨
- 사탕상자
- 백준 1106
- boj 16562
- 터보소트
- 제로베이스 스쿨
- boj 10775
- 부트 캠프
- 백준 3006
- 백준 12713
- 백준 10775
- boj 2336
- boj 12713
- boj 10473
- Ugly Numbers
- boj 1280
- 백준 10473
- boj 14868
- 백준 16562
- 디지털 비디오 디스크
- 백준 1280
- boj 1106
- 백준 2336
- boj 9345
- 백준 2243
- boj 2243
- 인간 대포
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함