트리
5639_이진검색트리
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 자 이번에는 이진검색트리이다. 이진검색트리는 루트 노드가 왼쪽노드보다는 무조건 크고, 오른쪽 노드보다는 무조건 작은 수가 들어있는 트리이다. 결국 전위탐색이던 중위탐색이던 후위탐색이던 다른 탐색으로 찾으려면 왼쪽노드와 오른쪽 노드가 갈라지는 경계점과 루트노드를 찾아야 한다. 전위탐색으로 시작을 했으므로 값을 담아둔 해당 리스트에서 가장 앞의 값이 루트노드일 것이고, 해당 노드의 값보다..
2263_트리의 순회 (메모리초과 나온다면?)
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 이번에는 트리의 순회 문제였다. 트리 구조를 보면 특징이 하나있다. 바로 트리를 잘라서 봐도 트리구조란 것 이전 문제에서 본 트리를 잠깐 보자면, 하나의 큰 트리는 작은 트리로 쪼갤 수 있다. 지금은 A가 루트인 트리이지만 C가 최고위의 트리와 B가 최고위인 트리 두개가 합쳐진 형태라고도 볼 수 있다. 그리고 전위,중위,후위 탐색은 특징이 있다. 전위 : 루트 + 왼쪽 + 오른쪽 중위 : 왼쪽 + 루트 + 오른쪽 후위 : ..