문제 링크

프로그래머스 문제

풀이

문제를 이해하기는 크게 어렵지 않다.
두가지 큰 조건을 만족시키면 되는데, 그 두가지는
1. 이진트리를 만들것
2. 이진트리에 따른 순회를 만족시킬것

1. 이진트리의 노드에 필요한 조건들

• constructor
  - index, x, y, left, right
• insert
  - leftInsert , rightInsert

2. 순회에 필요한 조건들

• 전위순회 (root -> left -> right)
• 후위순회 (left -> right -> root)
• 중위순회 (left -> root -> right)

결국 풀이를 생각해내지 못한채, 이분의 코드를 참고하게 되었습니다.

코드

class Node {
  constructor(index, valueX) {
    this.index = index;
    this.valueX = valueX;
    this.left = null;
    this.right = null;
  }

  insert(index, valueX) {
    this.valueX > valueX
      ? this.addLeft(index, valueX)
      : this.addRight(index, valueX);
  }

  addLeft(index, valueX) {
    this.left
      ? this.left.insert(index, valueX) // 일종의 제귀함수와 같은것이다. 왼쪽의 node에서 반복 실행시킨다. 
      : (this.left = new Node(index, valueX));
  }

  addRight(index, valueX) {
    this.right
      ? this.right.insert(index, valueX)
      : (this.right = new Node(index, valueX));
  }
}

function preOrder(binaryTree, arr) {
  if (binaryTree !== null) {
    arr.push(binaryTree.index); // 각각의 결과를 preArr에 저장
    preOrder(binaryTree.left, arr);
    preOrder(binaryTree.right, arr);
  }
}

function postOrder(binaryTree, arr) {
  if (binaryTree !== null) {
    postOrder(binaryTree.left, arr);
    postOrder(binaryTree.right, arr);
    arr.push(binaryTree.index); // 각각의 결과를 postArr에 저장
  }
}

function solution(nodeinfo) {
  let preArr = [];
  let postArr = [];

  let nodeWithIndex = nodeinfo.map((node, index) => [
    index + 1,
    node[0],
    node[1],
  ]);
  let sortedNode = nodeWithIndex.sort((a, b) => b[2] - a[2]);

  const binaryTree = new Node(sortedNode[0][0], sortedNode[0][1]);
  for (let i = 1; i < sortedNode.length; i++) {
    // 이진 트리를 조건에 맞게 구현
    binaryTree.insert(sortedNode[i][0], sortedNode[i][1]); // Node를 연결할 때 기준을 x좌표를 기준으로 left, right를 판단
  }

  preOrder(binaryTree, preArr); // 전위 순회
  postOrder(binaryTree, postArr); // 후위 순회

  return [preArr, postArr];
}

Reference

• velog의 다른 분 풀이