놓친부분에 대해서

1. 노드를 구성한후, y값이 가장 큰 노드를 정해야 하는데, 어떻게 찾을 것인가?
   -> 정렬하자!
   -> y가 가장 높은 값이 앞쪽 인덱스에 위치하게 하고, x값이 동일하다면,
   이진트리 확정이므로 ,x값이 작은 순서대로 정렬하자.

2. 노드간 연결 할때 어떻게 할 것이냐? 에 대해서
   루트 노드 하나와 순차적으로 자식 값들 비교해서 진행하자

풀이전략

• 이진트리를 만들어 나가는 과정이다.
• 핵심은 노드들을 어떻게 정렬하는지가 관건이다.
  -> 문제와 그림을 보고 생각해야 한다.

문제의 힌트에서
반드시 서로 다른 x값을 가진다라는 점 이라는 것을 알고 나면 이진트리
정의하는데 쉽게 조건 만들수 있다.

소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

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

void AddNode(Node *root, Node *child)
{
    //루트 노드의 오른쪽에 자식을 위치하자.
    if(root->x < child->x)
    {
        if(root->right == nullptr)
        {
            root->right = child;
        }
        else
        {
            AddNode(root->right, child);
        }
    }
    //루트 노드의 왼쪽에 자식을 위치하자.
    else
    {
        if(root->left == nullptr)
        {
            root->left = child;
        }
        else
        {
            AddNode(root->left, child);
        }
    }
}

void PreOrder(Node *cur, vector<int>&v)
{
    if(cur == nullptr)
        return;
    v.push_back(cur->num);
    PreOrder(cur->left, v);
    PreOrder(cur->right, v);
}

void PostOrder(Node *cur, vector<int>&v)
{
    if(cur == nullptr)
        return;
    
    PostOrder(cur->left, v);
    PostOrder(cur->right, v);
    v.push_back(cur->num);
}


vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    
    vector<Node> v(nodeinfo.size());
    
    for(int i = 0; i < nodeinfo.size(); i++)
    {
        v[i].num = i + 1;
        v[i].x = nodeinfo[i][0];
        v[i].y = nodeinfo[i][1];
    }
    
    sort(v.begin(), v.end(), compare);
    
    //연결리스트로 연결하자.
    
    Node *Root = &v[0];
    
    for(int i = 1; i< v.size(); i++)
    {
        AddNode(Root, &v[i]);
    }
    
    vector<int>pre;
    //전위 순회, 후위 순회 진행하자.
    PreOrder(Root, pre);
    
    vector<int>post;
    PostOrder(Root, post);
    
    answer.push_back(pre);
    answer.push_back(post);
    
    
    return answer;
}