D+39 트리순회 js (전위/중위/후위)순회

문제

이진 트리를 표현한 배열 nedes를 인자로 받습니다.
예를 들어서 nodes가 [1,2,3,4,5,6,7]이면 해당 이진 트리에 대하여 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 solution()함수를 구현하세요

제약조건
입력 노드값의 개수는 1개 이상 1,000개 이하다
노드값은 정수형이며 중복되지 않는다

문제 분석하고 풀기
말 그대로 전위, 중위, 후외 순회를 반환하면 되는 문제

function preorder(nodes, idx) {
  // idx가 노드 배열의 길이보다 작을 떄 
  if(idx <nodes.length){
    // 루트 노드를 출력한 다음, 
    //왼쪽 오른쪽 서브트리를 재귀 호출하여 출력 순서대로 이어붙임 
    let ret = `${nodes[idx]}`
    ret += preorder(nodes, idx*2+1);
    ret += preorder(nodes, idx*2+2);
    return ret;
  }
  // idx>= nodes.length일 때는 빈 문자열 반환
  reutn ""; 
  
}

function inorder(nodes, idx){
  // idx가 노드 배열의 길이보다 작을 때
  if (idx < nodes.length) {
    // 왼쪽 서브 트리를 먼저 재귀호출하여 출력 순서대로 이어붙임
    let ret=inorder(nodes, idx*2+1);
    // 루트 노드를 출력한 다음 오른쪽 서브 트리를 재귀호출하여 
    // 출력 순서대로 이어붙임 
    ret += `${nodes[idx]}`
    ret += inorder(nodes, idx*2+2);
    return ret;
  }
  // idx >= nodes.length일 때는 빈 문자열 반환 
  return ""; 
}

function postorder(nodex,idx){
  // idx가 노드 배열의 길이보다 작을 때 
  if(idx< nodes.length){
    // 왼쪽 서브 트리와 오른쪽 서브 트리를 재귀 호출하여 출력 순서대로 이어붙임
    let ret=postorder(nodes,idx*2+1);
    ret += postorder(nodes, idx*2+2);
    ret += `${nodes[idx]}`
    return ret
  }
  // idx>=nodes.length일 때는 빈 문자열 반환
  return ""; 
}

function solution(nodes){
  // 전위 순회, 중위 순회, 후위 순회 결과 계산
  // 노드 배열과 루트 노드의 인덱스를 매개변수로 각각 호출
  return [
    preorder(nodes,0).slice(0,-1), // 마지막 공백 제거
    inorder(nodes,0).slice(0,-1), // 마지막 공백 제거
    postorder(nodes,0).slice(0,-1)
  ]
}

위 코드는 nodes는 노드 배열을 의미하며 solution()함수에서는 이 nodes 배열과 루트 노드의 인덱스를 preorder(), inorder(), postorder() 함수에 인수로 전달하여 전위 순회, 중위 순회, 후위 순회 결과를 각각 계산하고 이를 배열로 반환한다.

preorder(), inorder(), postorder() 함수에서는 idx가 노드배열 길이보다 작을 때만 재귀 호출하도록 하며 idx가 노드 배열의 길이와 같거나 크면 빈 문자열을 반환한다.
solution()함수에서는 반환된 결과 문자열에서 마지막 공백을 제거한 뒤 배열로 반환한다.

이 문제의 핵심은 '배열로 표현한 이진 트리를 순회하는 코드를 구현하라' 이다. 앞서 배열로 트리를 표현할 때 루트 노드가 인덱스 0이 될 수도, 인덱스 1이 될 수도 있지만 1을 자주 쓴다고 했다. 여기서는 1이 아닌 0을 쓰는 경우를 보여주기 위해 루트 노드의 인덱스를 0으로 하였다.