프로그래머스 Level 3 - 길 찾기 게임
📌 문제 설명
📌 생각한 풀이 방법
- 이진 트리를 조건에 맞게 구현한다.
- Node를 연결할 때 기준을 x좌표를 기준으로 left, right를 판단한다.
- 이진 트리를 생성한 후, 전위 순회, 후위 순회를 한다.
- 각각의 결과를 preArr, postArr에 저장한 후 [preArr,postArr]를 반환한다.
📌 풀이
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)
: (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);
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);
}
}
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]);
}
preOrder(binaryTree, preArr);
postOrder(binaryTree, postArr);
return [preArr, postArr];
}