문제링크

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

구현방법

힌트 보기전 생각

1. 2차원 좌표값을 통해서 노드의 간선을 이어준다.

2. 노드의 간선을 이어준 것을 토대로 2가지의 순회를 구한다.

   1. 전위순회
   2. 후위순회

3. 각 결과 순회를 받아놓는다.

class Node를 생성

x값이 값을 의미하고 y값이 노드 레벨

left노드 right 노드 를만들어서 진행

알고리즘

• 트리를 만든다.
• class 통해서 노드를 만든다.

트리 구조를 이해하고 만든다음 -> 순회 방법을 알면 풀수있다.

---

힌트 사용: https://taehoung0102.tistory.com/205

자바로 트리 구조를 직접 구현해본 적은 별로 없었기 때문에 다른 분의 코드를 보면서 진행했습니다.

구현알고리즘

트리

CODE

import java.util.*;

class Solution {
    int[][] result;
    int index = 0;


    public int[][] solution(int[][] nodeinfo) {
        int[][] answer = {};

        Node[] nodes = new Node[nodeinfo.length];

        for(int idx = 0; idx <nodeinfo.length;idx++){
            nodes[idx] = new Node(idx+1,nodeinfo[idx][0],nodeinfo[idx][1],null,null);
        }

        Arrays.sort(nodes, (o1, o2) -> {

            if(o1.y == o2.y){
                return o1.x - o2.x;
            }
            return o2.y - o1.y;
        });

        Node parent = nodes[0];

        for(int idx =1;idx <nodes.length;idx++){
            MakeTree(parent,nodes[idx]);
        }

        result = new int[2][nodeinfo.length];
        preorder(parent);
        index=0;
        postorder(parent);

        answer =result;
        return answer;
    }

    //트리 만들기(핵심 로직)
    //현재 기준에서 parent x보다 크면 right 작으면 left
    private void MakeTree(Node parent, Node node) {
        if(parent.x < node.x){
            if(parent.right == null){
                parent.right = node;
                //연결된것이 있는경우 다음 노드로 가서 진해
                //연결된것이 있는경우 다음 노드로 가서 진해
            }else{
                MakeTree(parent.right,node);
            }

        }

        //left부분도 같은 수순으로 진행
        else{
            if(parent.left == null){
                parent.left = node;
            }else{
                MakeTree(parent.left,node);
            }
        }
    }

    //전위순회
    public void preorder(Node root){
        if(root != null){
            result[0][index++] = root.value;
            preorder(root.left);
            preorder(root.right);
        }
    }

    public void postorder(Node root){
        if(root != null){
            postorder(root.left);
            postorder(root.right);
            result[1][index++] = root.value;
        }
    }

    //핵심 클래스
    class Node {
        public int value;
        public int x;
        public int y;

        //좌우 노드 
        public Node right;
        public Node left;


        public Node(int value, int x, int y, Node right, Node left) {
            this.value = value;
            this.x = x;
            this.y = y;
            this.right = right;
            this.left = left;
        }
    }
}