길 찾기 게임

문제 설명
길 찾기 게임

다음 규칙으로 트리 노드들을 구성한다.

트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
모든 노드는 서로 다른 x값을 가진다.
같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
자식 노드의 y 값은 항상 부모 노드보다 작다.
임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
아래 예시를 확인해보자.

위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.

전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때,
노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.

구현문제이다. 결국 x의 값으로 다음 노드의 위치를 구할수 있으므로 y의 좌표로 정렬한 값을 트리화 시킬수 있다면 문제를 풀수있다.
최대한 전역변수를 사용하지 않고 풀려고하다보니 idx의 값을 preorder와 postorder에 넣었을때 문제가 발생했다 다음으로 진행한다고해도 재귀적으로 진행된 함수를 생각하면 다음값이 무조건 증가하지 않는걸 간과했다. 따라서 arrayList를 통해 저장후 변환하는 방식으로 해결했다.

코드

import java.util.*;
class Solution {   
    public int[][] solution(int[][] nodeinfo) {
        Node[] node =new Node[nodeinfo.length];
         int[][] answer = new int[2][nodeinfo.length];
        
        for(int i=0;i<nodeinfo.length;i++){
            node[i]= new Node(nodeinfo[i][0],nodeinfo[i][1],i+1,null,null);
        }
        

        Arrays.sort(node,(o1,o2)->o2.y-o1.y);      
        Node tree = node[0];
        for(int i=1;i<nodeinfo.length;i++){
            insertNodetree(tree,node[i]);
        }
        ArrayList<Integer> list = new ArrayList<>();
        preorder(tree,list);
        answer[0]=list.stream().mapToInt(Integer::intValue).toArray();
        list.clear();
        postorder(tree,list);   
        answer[1]=list.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
    
    
    public void preorder(Node node,ArrayList<Integer> list){
        if(node!=null){
            list.add(node.value);
            preorder(node.left,list);
            preorder(node.right,list);
        }
    }
    
    public void postorder(Node node,ArrayList<Integer> list){
         if(node!=null){
            postorder(node.left,list);
            postorder(node.right,list);
            list.add(node.value);
        }
    }
    public void insertNodetree(Node tree,Node node){
        if(tree.x>node.x){
            if(tree.left==null) tree.left=node;
            else insertNodetree(tree.left,node);
        }else{
            if(tree.right==null) tree.right=node;
            else insertNodetree(tree.right,node);
        }
    }
    public class Node{
        int x;
        int y;
        int value;
        Node right;
        Node left;
        public Node(int x,int y,int value,Node right,Node left){
            this.x=x;
            this.y=y;
            this.value=value;
            this.right=right;
            this.left=left;
        }
    }
}