import java.util.*;
class Solution {
public int[][] solution(int[][] nodeInfos) {
//트리 구성하고 전위, 후위 결과를 리넡하면됨
//트리 구성하기
//0 우선순위큐에 넣기
int idx = 1;
PriorityQueue<Node> pq = new PriorityQueue<>();
for(int[] info : nodeInfos){
pq.add(new Node(info[0], info[1], idx++));
}
//1 루트 노드 찾기
Node root = pq.poll();
//2 루트 노드에서 부터 재귀 함수 적용하기
makeBinaryTree(root, pq);
//3 재귀 함수는 y가 가장 큰거를 빼면되는대 최소0개 최대2개 뺄수있다.
// 이거 우선순위 큐 쓰면될거같다. 노드를 큐에넣고, y를 내림차순으로 하도록 하자.
// 노드에 있어야할 정보는 부모의 x가 있어야될듯
//트리만들었으니 이제 순회한다.
int[][] answer = new int[2][nodeInfos.length];
answer[0] = pre(root, new ArrayList<Integer>());
answer[1] = post(root, new ArrayList<Integer>());
return answer;
}
//전위 D L R
private static int[] pre(Node node, List<Integer> box){
box.add(node.idx);
if(node.left != null){
pre(node.left, box);
}
if(node.right != null){
pre(node.right, box);
}
int[] result = new int[box.size()];
for(int i=0 ; i<result.length ; i++){
result[i] = box.get(i);
}
return result;
}
//후위 L R D
private static int[] post(Node node, List<Integer> box){
if(node.left != null){
post(node.left, box);
}
if(node.right != null){
post(node.right, box);
}
box.add(node.idx);
int[] result = new int[box.size()];
for(int i=0 ; i<result.length ; i++){
result[i] = box.get(i);
}
return result;
}
private static void makeBinaryTree(Node parent, PriorityQueue<Node> pq){
int parentY = parent.y;
List<Node> childNodes = new ArrayList<>();
//비었으면 트리 완성임
if(pq.isEmpty()) return;
int stdY = pq.peek().y;
while(!pq.isEmpty() && pq.peek().y == stdY){
childNodes.add(pq.poll());
}
//좌측 자식 찾기
Node left = null;
for(Node child : childNodes){
//부모x 세팅한다.
child.parentX = parent.x;
if( && child.x < parent.x){
parent.left = child;
makeBinaryTree(child, pq);
}else{
parent.right = child;
makeBinaryTree(child, pq);
}
}
//우측 자식 찾기
//본격적 엮는다.
//범위: 좌측일때 - 본인 - 부모x , 우측일때 부모 - 본인 -
for(Node child : childNodes){
//부모x 세팅한다.
child.parentX = parent.x;
if(child.x < parent.x){
parent.left = child;
makeBinaryTree(child, pq);
}else{
parent.right = child;
makeBinaryTree(child, pq);
}
}
}
static class Node implements Comparable<Node>{
int x,y,parentX,idx;
Node left;
Node right;
Node(int x, int y, int idx){
this.x = x;
this.y = y;
this.idx = idx;
}
@Override
public int compareTo(Node other){
return other.y - this.y;
}
}
}답지보고 insert 메서드 적용하니 성공한다.
import java.util.*;
class Solution {
public int[][] solution(int[][] nodeInfos) {
//트리 구성하고 전위, 후위 결과를 리넡하면됨
//트리 구성하기
//0 우선순위큐에 넣기
int idx = 1;
PriorityQueue<Node> pq = new PriorityQueue<>();
for(int[] info : nodeInfos){
pq.add(new Node(info[0], info[1], idx++));
}
//1 루트 노드 찾기
Node root = pq.poll();
//2 루트 노드에서 부터 재귀 함수 적용하기
makeBinaryTree(root, pq);
//3 재귀 함수는 y가 가장 큰거를 빼면되는대 최소0개 최대2개 뺄수있다.
// 이거 우선순위 큐 쓰면될거같다. 노드를 큐에넣고, y를 내림차순으로 하도록 하자.
// 노드에 있어야할 정보는 부모의 x가 있어야될듯
//트리만들었으니 이제 순회한다.
int[][] answer = new int[2][nodeInfos.length];
answer[0] = pre(root, new ArrayList<Integer>());
answer[1] = post(root, new ArrayList<Integer>());
return answer;
}
//전위 D L R
private static int[] pre(Node node, List<Integer> box){
box.add(node.idx);
if(node.left != null){
pre(node.left, box);
}
if(node.right != null){
pre(node.right, box);
}
int[] result = new int[box.size()];
for(int i=0 ; i<result.length ; i++){
result[i] = box.get(i);
}
return result;
}
//후위 L R D
private static int[] post(Node node, List<Integer> box){
if(node.left != null){
post(node.left, box);
}
if(node.right != null){
post(node.right, box);
}
box.add(node.idx);
int[] result = new int[box.size()];
for(int i=0 ; i<result.length ; i++){
result[i] = box.get(i);
}
return result;
}
private static void makeBinaryTree(Node root, PriorityQueue<Node> pq){
while(!pq.isEmpty()){
insert(root, pq.poll());
}
}
private static void insert(Node root, Node node){
if(node.x < root.x){
if(root.left == null){
root.left = node;
}else{
insert(root.left, node);
}
}else{
if(root.right == null){
root.right = node;
}else{
insert(root.right, node);
}
}
}
static class Node implements Comparable<Node>{
int x,y,parentX,idx;
Node left;
Node right;
Node(int x, int y, int idx){
this.x = x;
this.y = y;
this.idx = idx;
}
@Override
public int compareTo(Node other){
return other.y - this.y;
}
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
private static class Node {
public final int value;
public final int x;
public final int y;
public Node left;
public Node right;
private Node(int value, int x, int y) {
this.value = value;
this.x = x;
this.y = y;
}
}
private void insert(Node root, Node node) {
if (node.x < root.x) {
if (root.left == null) {
root.left = node;
} else {
insert(root.left, node);
}
} else {
if (root.right == null) {
root.right = node;
} else {
insert(root.right, node);
}
}
}
private Node constructTree(Node[] nodes) {
Node root = nodes[0];
for (int i = 1; i < nodes.length; i++) {
insert(root, nodes[i]);
}
return root;
}
private void pre(Node node, List<Integer> visits) {
if (node == null) return;
visits.add(node.value);
pre(node.left, visits);
pre(node.right, visits);
}
private void post(Node node, List<Integer> visits) {
if (node == null) return;
post(node.left, visits);
post(node.right, visits);
visits.add(node.value);
}
public int[][] solution(int[][] nodeInfo) {
Node[] nodes = new Node[nodeInfo.length];
for (int i = 0; i < nodes.length; i++) {
nodes[i] = new Node(i + 1, nodeInfo[i][0], nodeInfo[i][1]);
}
Arrays.sort(nodes, (a, b) -> b.y - a.y);
Node root = constructTree(nodes);
List<Integer> preorder = new ArrayList<>();
pre(root, preorder);
List<Integer> postorder = new ArrayList<>();
post(root, postorder);
return new int[][]{
preorder.stream().mapToInt(Integer::intValue).toArray(),
postorder.stream().mapToInt(Integer::intValue).toArray(),
};
}
}