[이진 트리] (CHECK) 프로그래머스 길 찾기 게임 C++

 

https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<vector<int>> answer(2);

struct Node {
    int x, y, key;
    Node* left;
    Node* right;
    
    Node(int x, int y, int key) : x(x), y(y), key(key), left(NULL), right(NULL) {}
};

bool comp(vector<int> a, vector<int> b) {
    if (a[1] != b[1]) return a[1] > b[1]; // 내림차순
    return a[0] < b[0]; // 오름차순
}

void insertNode(Node* root, vector<int> info) {
    if (root->x > info[0]) {
        if (root->left == NULL) root->left = new Node(info[0], info[1], info[2]);
        else insertNode(root->left, info);
    }
    else {
        if (root->right == NULL) root->right = new Node(info[0], info[1], info[2]);
        else insertNode(root->right, info);
    }
}

void order(Node* root) {
    if (root == NULL) return;
    answer[0].push_back(root->key); // 전위 순회
    order(root->left);
    order(root->right);
    answer[1].push_back(root->key); // 후위 순회
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    n = nodeinfo.size(); // 원소 개수
    for(int i=0; i<n; i++) nodeinfo[i].push_back(i+1); // 노드 번호
    
    sort(nodeinfo.begin(), nodeinfo.end(), comp); // y 내림차순 정렬
    
    Node* root = new Node(nodeinfo[0][0], nodeinfo[0][1], nodeinfo[0][2]);
    for(int i=1; i<n; i++) insertNode(root, nodeinfo[i]); // root 제외
    
    order(root);
    
    return answer;
}