문제

카카오 프로그래머스

풀이

문제를 보고 이진트리에 관한 문제라는 것은 알았으나... 이진트리 풀이에 대해 학습을 하지 못해서 유투브 영상을 참고했다.

#include <string>
#include <vector>
#include <algorithm> 

using namespace std;

typedef struct Node {
	int id;
	int x;
	int y;
	Node* left;
	Node* right;
}node;

bool ft_compare(node& a, node& b) {
	if (a.y == b.y)
		return a.x < b.x;
	return a.y > b.y;
}

void addNode(node* parent, node* child) {
	if (child->x < parent->x) {
		if (parent->left == NULL)
			parent->left = child;
		else
			addNode(parent->left, child);
	}
	else {
		if (parent->right == NULL)
			parent->right = child;
		else
			addNode(parent->right, child);
	}
}

void preorder(vector<int>& ans, node* nodes) {
	if (nodes == NULL) return;
	
	ans.push_back(nodes->id);
	preorder(ans, nodes->left);
	preorder(ans, nodes->right);
}

void postorder(vector<int>& ans, node* nodes)
{
	if (nodes == NULL) return;

	postorder(ans, nodes->left);
	postorder(ans, nodes->right);
	ans.push_back(nodes->id);

}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
	vector<vector<int>> answer{ {}, {} };
	int size = nodeinfo.size();
	vector<node> nodes;

	for (int i = 0; i < size; i++) {
		nodes.push_back({ i + 1, nodeinfo[i][0], nodeinfo[i][1] });
	}
	sort(nodes.begin(), nodes.end(), ft_compare);

	node* root = &nodes[0];
	for (int i = 1; i < size; i++) {
		addNode(root, &nodes[i]);
	}
	preorder(answer[0], root);
	postorder(answer[1], root);

	return answer;
}

int main()
{
	vector<vector<int>> v = { {5, 3}, {11, 5}, {13 ,3} };
	vector<vector<int>> s = solution(v);
}