[BOJ / C++] 26260 - 이가 빠진 이진트리

백준 문제 링크 : 26260 - 이가 빠진 이진트리

문제

다 쓰기 갑자기 귀찮아졌으니 거두절미하겠습니다.

대충 뭐냐면.. 이진트리의 리프 노드 하나를 가려버리고 다른 숫자로 바꿔끼우면 트리가 어떻게 변하는지 보고싶다고 합니다.

따라서 입력으로
노드의 개수 $N$, 레벨순회 결과 (이 때, 가려진 리프노드는 -1로 입력), 그리고 -1이 있는 자리에 새로 끼울 정수
이렇게 주어집니다

풀이

먼저, 입력이 레벨순회로 들어오며 노드의 개수 $N$이 정해져 있으므로 배열로 이진트리를 구현하도록 합니다.
배열로 이진트리를 구성하면

• $n+1$만큼의 배열을 만들고, 0번 자리는 비운다
• $i$번째 원소의 부모는 $i/2$의 floor
• $i$번째 원소의 왼쪽 자식은 $2 * i$, 오른쪽 자식은 $2 * i + 1$ .
• 레벨순회 순서의 입력은 순서대로 배열에 넣으면 이진트리가 완성됨

이제 배열 트리를 만들었고, -1 자리 대신 들어갈 정수를 $X$라고 한다면..
이 $X$가 들어갔을 때 이진트리의 특성을 유지하게끔 하기 위해, 재조정과정을 거칩니다.
그 과정은 중위순회와 역중위순회를 이용하도록 합니다

1. 먼저 중위순회를 돌며, 이가 빠진 부분(-1인 곳)까지 순회하며 만약 $X$보다 큰 원소가 있는 경우 교체
2. 그 후, 역중위순회를 돌며, 이가 빠진 부분(-1인 곳)까지 순회하며 만약 $X$보다 작은 원소가 있는 경우 교체
3. 위 과정이 모두 끝나면 이가 빠진 자리는 $X$가 들어가기 적절한 자리가 되므로, $X$를 집어넣으면 됩니다.

이 과정이 끝났으면 문제의 출력 요구사항대로 후위순회하여 결과를 보여주면 끝

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

int flag = -1;
int x;

void r_inorder(vector<int> &tree, int current, int n) {
	if (current < 1 || current > n) return;
	r_inorder(tree, current*2+1, n);
	if (tree[current] == -1) {
		flag = 0;
		tree[current] = x;
	}
	if (flag == -1) {
		if (tree[current] < x) swap(tree[current], x);
	}
	r_inorder(tree, current*2, n);
}
void inorder(vector<int> &tree, int current, int n) {
	if (current < 1 || current > n) return;
	inorder(tree, current*2, n);
	if (flag == -1) {
		if (tree[current] > x) swap(tree[current], x);
	}
	inorder(tree, current*2+1, n);
}


void postorder(vector<int> &tree, int current, int n) {
	if (current < 1 || current > n) return;
	postorder(tree, current*2, n);
	postorder(tree, current*2+1, n);
	cout << tree[current] << " ";
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector<int>tree(n+1, 0);
	int index = 0;
	for(int i=1;i<=n;i++) {
		cin >> tree[i];
		if (tree[i] == -1) index = i;
	}
	cin >> x;
	inorder(tree, 1, n);
	r_inorder(tree, 1, n);
	postorder(tree, 1, n);
}