道を探すゲーム

プログラマー-道を探すゲーム

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    static class Tree {
	int idx, x, y;
	Tree left, right;

	Tree(int[] node) {
		this.x = node[0];
		this.y = node[1];
		this.idx = node[2];
	}

	Tree findParend(int x, int y) { // 부모 찾기
		Tree tmp = x < this.x ? left : right;
		if (tmp == null)
			return this;
		while (tmp.y > y) {
			Tree child = x < tmp.x ? tmp.left : tmp.right;
			if (child == null)
				break;
			else
				tmp = child;
		}
		return tmp;
	}
}
    
    static ArrayList<Integer> list = new ArrayList<Integer>();
    public int[][] solution(int[][] nodeinfo) {
        int[][] idxNode = new int[nodeinfo.length][];
	for (int i = 0; i < nodeinfo.length; i++) {
		idxNode[i] = new int[] { nodeinfo[i][0], nodeinfo[i][1], i + 1 };
	}
	Arrays.sort(idxNode, (a,b) -> b[1]-a[1]); // y축으로 내림차순
	Tree root = new Tree(idxNode[0]); // y축 기준으로 제일 높은 root
		
	for (int i = 1; i < nodeinfo.length; i++) {// idx 1부터 시작
		int [] node = idxNode[i];
		Tree parent = root.findParend(node[0], node[1]);
		if(node[0] < parent.x) parent.left = new Tree(node);
		else parent.right = new Tree(node);
	}
		
	PreOrder(root);
	int [] pre = new int [nodeinfo.length];
	for (int i = 0; i < nodeinfo.length; i++) {
		pre[i] = list.get(i);
	}
	list = new ArrayList<>();
		
	PostOrder(root);
	int [] post = new int [nodeinfo.length];
	for (int i = 0; i < nodeinfo.length; i++) {
		post[i] = list.get(i);
	}
	int [][] answer = new int [][] {pre, post};
       return answer;
   }
    
    static void PreOrder(Tree t) { // 전위 순회
		list.add(t.idx);
		if(t.left != null) PreOrder(t.left);
		if(t.right != null) PreOrder(t.right);
	}
    
    static void PostOrder(Tree t) { // 후위 순회
		if(t.left != null) PostOrder(t.left);
		if(t.right != null) PostOrder(t.right);
		list.add(t.idx);
	}
    
}