길 찾기 게임 풀이

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

using namespace std;

struct Node {
	int num;
	int x, y;
	Node* left;
	Node* right;
};

bool cmp(Node a, Node b) {
	if (a.y > b.y)
		return true;
	else if (a.y == b.y)
		return a.x < b.x;
	else
		return false;
}

void sortnode(Node *parent, Node *child) {
	if (parent->x > child->x) {
		if (parent->left == NULL)
			parent->left = child;
		else
			sortnode(parent->left, child);
	}
	else {
		if (parent->right == NULL)
			parent->right = child;
		else
			sortnode(parent->right, child);
	}
}

void preorder(vector<int> &v,Node *root) {
	if (root == NULL)
		return;

	v.push_back(root->num);
	preorder(v, root->left);
	preorder(v, root->right);
}

void postorder(vector<int> &v, Node *root) {
	if (root == NULL)
		return;

	postorder(v, root->left);
	postorder(v, root->right);
	v.push_back(root->num);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
	vector<vector<int>> answer = { {},{} };
	vector<Node> node;
	
	for (int i = 0; i < nodeinfo.size(); i++)
		node.push_back({ i + 1, nodeinfo[i][0], nodeinfo[i][1] });

	sort(node.begin(), node.end(), cmp);

	Node *root = &node[0];
	for (int i = 1; i < node.size(); i++) {
		sortnode(root, &node[i]);
	}

	preorder(answer[0], root);
	postorder(answer[1], root);
	return answer;
}