길 찾기 게임

function NewNode(value, x, y) {
  this.val = value;

  this.x = x;
  this.y = y;

  this.left = null;
  this.right = null;

  this.insert = (value, x, y) => {
    if (this.x >= x) {
      if (this.left) this.left.insert(value, x, y);
      else this.left = new NewNode(value, x, y);
    } else {
      if (this.right) this.right.insert(value, x, y);
      else this.right = new NewNode(value, x, y);
    }
  };

  this.preOrder = (arr = []) => {
    arr.push(this.val);

    if (!this.left && !this.right) {
      return arr;
    }

    if (this.left) {
      this.left.preOrder(arr);
    }

    if (this.right) {
      this.right.preOrder(arr);
    }

    return arr;
  };

  this.postOrder = (arr = []) => {
    if (!this.left && !this.right) {
      arr.push(this.val);
      return arr;
    }

    if (this.left) {
      this.left.postOrder(arr);
    }

    if (this.right) {
      this.right.postOrder(arr);
    }

    arr.push(this.val);

    return arr;
  };

  return this;
}

const makeTree = (nodes) => {
  const { value, coord } = nodes[0]; // root 
  const [x, y] = coord;

  const tree = new NewNode(value, x, y); { x, y, val, left, right }

  for (let i = 1; i < nodes.length; i += 1) {
    const { value, coord } = nodes[i];
    const [x, y] = coord;

    tree.insert(value, x, y);
  }

  return tree;
};

const solution = (nodeinfo) => {
  const sortedNodeInfo = [...nodeinfo]
    .map((coord, index) => ({ value: index + 1, coord }))
    .sort((a, b) => {
      if (b.coord[1] !== a.coord[1]) return b.coord[1] - a.coord[1];

      return a.coord[0] - b.coord[0];
    });

  const tree = makeTree(sortedNodeInfo);

  return [tree.preOrder(), tree.postOrder()];
};

class Node {
    constructor(x, y, num){
        this.x = x;
        this.y = y;
        this.num = num;
        this.left = null;
        this.right = null;
    }
}

function solution(nodeinfo) {
    const answer = [[], []];
    const node = [];
    
    const addNode = (parent, child) => {
        if(child.x < parent.x){
            if(parent.left === null){
                parent.left = child;
            } else{
                addNode(parent.left, child);
            }
        } else{
            if(parent.right === null){
                parent.right = child;
            } else{
                addNode(parent.right, child);
            }
        }
    }
    
    const preorder = (node) => {
        if(node === null){
            return;
        }
        
        answer[0].push(node.num);
        preorder(node.left);
        preorder(node.right);
    }
    
    const postorder = (node) => {
        if(node === null){
            return;
        }
        
        postorder(node.left);
        postorder(node.right);
        answer[1].push(node.num);
    }
    
    for(let i = 0; i < nodeinfo.length; i++){
        const [x, y] = nodeinfo[i];
        const num = i + 1;
        const tmpNode = new Node(x, y, num);
        
        node.push(tmpNode);
    }
    
    node.sort((a, b) => {
        if(a.y === b.y){
            return a.x - b.x;
        }
        
        return b.y - a.y;
    });
    
    const root = node[0];
    
    for(let i = 1; i < node.length; i++){
        addNode(root, node[i]);
    }
    
    preorder(root);
    postorder(root);
    
    return answer;
}

function solution (nodeinfo) {
  const preorderArr = [];
  const postorderArr = [];
  
  const nodes = nodeinfo.map((node, idx) => [ idx+1, node[0], node[1] ])
  			.sort((a, b) => b[2] - a[2]);
  
  const bTree = new BinaryTree(nodes[0][0], nodes[0][1]);
  for(let i = 1; i < nodes.length; i++) {
    bTree.insert(nodes[i][0], nodes[i][1]);
  }
  
  preorder(bTree, preorderArr);
  postorder(bTree, postorderArr);
  
  return [preorderArr, postorderArr];
}

class BinaryTree {
  constructor(value, x_pos) {
    this.value = value;
    this.x_pos = x_pos;
    this.left = null;
    this.right = null;
  }
  
  insert(value, x_pos) {
    this.x_pos >= x_pos
    	? this._toLeft(value, x_pos)
    	: this._toRight(value, x_pos);
  }
  
  _toLeft(value, x_pos) {
    this.left 
    	? this.left.insert(value, x_pos)
    	: this.left = new BinaryTree(value, x_pos);
  }
  
  _toRight(value, x_pos) {
    this.right
    	? this.right.insert(value, x_pos)
    	: this.right = new BinaryTree(value, x_pos);
  }
}

const preorder = (bTree, arr) => {
  if(bTree !== null) {
    arr.push(bTree.value);
    preorder(bTree.left, arr);
    preorder(bTree.right, arr);
  }
}

const postorder = (bTree, arr) => {
  if(bTree !== null) {
    postorder(bTree.left, arr);
    postorder(bTree.right, arr);
    arr.push(bTree.value);
  }
}