이것 저것 &

문제링크: https://www.acmicpc.net/problem/4256

접근방식

1. 두 가지 순회방법을 통해서 남은 한가지 순회방법을 찾을 수 있다.

전위는 root노드 - root기준 왼쪽 자식노드 - root기준 오른쪽 자식노드 순으로 표시되고

중위는 root기준 왼쪽 자식노드 - root노드 - root기준 오른쪽 자식노드 순으로 표시된다.

-> 그렇다면 후위순회 함수를 구현하며 노드 값을 출력하며 결과를 도출할 수 있다. 

2. 전위 순회함수로 탐색을 하며 root값에 해당하는 중위순회값을 매개변수로 전달하며 진행

3. 재귀함수, 분할정복으로 구현하였다.

문제풀이 

1. 분할정복으로 구현 

2. 전위순회를 기준으로 root 노드를 출력하는 형태

아래는 정답 코드입니다.

#include <iostream>
using namespace std;

int t;
int n;
int pre[1000] = { 0, };
int ino[1000] = { 0, };

void solved(int pl, int pr, int il, int ir) {
	if ((pr - pl) == 0) {
		cout << pre[pl] << ' ';
		return;
	}

	for (int i = 0; i <= pr - pl; i++) {
		if (pre[pl] == ino[il + i]) {
			solved(pl + 1, pl + i, il, il + i - 1);
			solved(pl + i + 1, pr, il + i + 1, ir);
			cout << pre[pl] << ' ';
			return;
		}

	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> t;

	while (t--) {
		cin >> n;

		for (int i = 0; i < n; i++)
			cin >> pre[i];
		for (int i = 0; i < n; i++)
			cin >> ino[i];

		solved(0, n - 1, 0, n - 1);
		cout << "\n";
	}

	cout << "\n";
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1068

리프노드의 갯수를 구하는 문제입니다.

dfs 탐색을 통해서 제거된 노드의 자식노드들도 함께 제거를 하면 진행해주었습니다.

만약, 자식 노드를 가지고 있지 않다면 leaf 노드로 간주했습니다.

이때, 주의할 점은 제거된 노드의 부모노드가 leaf 노드가 될 수 있다는 점입니다.

아래는 정답 코드입니다.

#include <iostream>
#include <vector>
using namespace std;

vector <int> vec[50];
int n = 0, root;

void dfs(int n) {

	if (vec[n].size() == 0) {
		vec[n].push_back(-2);
		return;
	}
	for (int i = 0; i < vec[n].size(); i++) {
		dfs(vec[n][i]);
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		if (temp == -1) 
			root = i;
		else
			vec[temp].push_back(i);
	}
	int m;
	cin >> m;

	dfs(m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < vec[i].size(); j++) {
			if (vec[i][j] == m)
				vec[i].erase(vec[i].begin() + j);
		}
	}
	int result = 0;
	for (int i = 0; i < n; i++)
		if (vec[i].size() == 0)
			result++;
	cout << result << endl;

	return 0;
}