[JS] 코딩 테스트 문제 : 이진트리 순회 [깊이우선탐색]

문제 : 이진트리 순회(깊이우선탐색)

문제 설명

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

전위순회 출력 : 1 2 4 5 3 6 7
중위순회 출력 : 4 2 5 1 6 3 7
후위순회 출력 : 4 5 2 6 7 3 1

내코드

function solution(n, end) {
  let preorderAnswer = "";
  let inorderAnswer = "";
  let postorderAnswer = "";

  // 트리 생성부분
  let tree = [];
  let current = 1; // 현재 입력될 숫자를 의미

  // n 부터 end 만큼 반복하면서 이진트리 생성 num 현재 노드를 의미
  // tree 배열의 주소 index 와 노드의 값이 같아 index 값이 즉 index 값을 가진 노드를 의미한다.
  for (let num = n; num <= end; num++) {
    tree.push({
      root: num,
      l: current < end ? ++current : null,
      r: current < end ? ++current : null,
    });
  }

  console.log(tree);

  // 전위순회
  function preorder(obj) {
    // 현재 노드의 값을 정답 문자열에 추가
    preorderAnswer += obj.root + " ";
    console.log("# root", obj);

    // 왼쪽 노드가 있다면 왼쪽노드를 활용해 재귀적으로 함수 호출
    obj.l && preorder(tree[obj.l - 1]);

    // 오른쪽 노드가 있다면 오른쪽노드를 활용해 재귀적으로 함수 호출
    obj.r && preorder(tree[obj.r - 1]);
  }

  // 중위순회
  function inorder(obj) {
    console.log("# root", obj);

    // 왼쪽 노드가 있다면 왼쪽노드를 활용해 재귀적으로 함수 호출
    obj.l && inorder(tree[obj.l - 1]);

    // 현재 노드의 값을 정답 문자열에 추가
    inorderAnswer += obj.root + " ";

    // 오른쪽 노드가 있다면 오른쪽노드를 활용해 재귀적으로 함수 호출
    obj.r && inorder(tree[obj.r - 1]);
  }

  // 후위순회
  function postorder(obj) {
    console.log("# root", obj);

    // 왼쪽 노드가 있다면 왼쪽노드를 활용해 재귀적으로 함수 호출
    obj.l && postorder(tree[obj.l - 1]);

    // 오른쪽 노드가 있다면 오른쪽노드를 활용해 재귀적으로 함수 호출
    obj.r && postorder(tree[obj.r - 1]);

    // 현재 노드의 값을 정답 문자열에 추가
    postorderAnswer += obj.root + " ";
  }

  preorder(tree[0]);
  console.log("전위순회 결과 출력 : " + preorderAnswer);

  inorder(tree[0]);
  console.log("중위순회 결과 출력 : " + inorderAnswer);

  postorder(tree[0]);
  console.log("후위순회 결과 출력 : " + postorderAnswer);
}
solution(1, 7);

풀이

1. 그림과 같은 트리를 구현하기 위해 tree 배열을 생성하고 현재 입력될 숫자를 의미할 current 변수를 1 로 초기화
2. n 부터 end 만큼 반복하면서 객체 형식의 노드를 생성해 노드의 값은 num 이며 좌측 자식 노드는 ++current, 우측 자식 노드를 한번 더 ++current 값을 지정 (tree 배열의 주소 index + 1 와 노드의 값이 같아 index + 1 값을 가진 노드를 의미한다.)
3. 순회 방식을 재귀 함수로 구현
   전위 순회 :
   1. 현재 노드의 값을 정답 문자열에 추가
   2. 왼쪽 노드가 있다면 왼쪽 노드를 재귀적으로 함수 호출
   3. 오른쪽 노드가 있다면 오른쪽 노드를 재귀적으로 함수 호출
   중위 순회 :
   1. 왼쪽 노드가 있다면 왼쪽 노드를 재귀적으로 함수 호출
   2. 현재 노드의 값을 정답 문자열에 추가
   3. 오른쪽 노드가 있다면 오른쪽 노드를 재귀적으로 함수 호출
   후위 순회 :
   1. 왼쪽 노드가 있다면 왼쪽 노드를 재귀적으로 함수 호출
   2. 오른쪽 노드가 있다면 오른쪽 노드를 재귀적으로 함수 호출
   3. 현재 노드의 값을 정답 문자열에 추가

오답 노트

// 초창기 코드
function solution(n, end) {
  let answer = "";

  // 0번째는 헤더를 가지는 트리 생성(연결리스트 head 느낌)
  let tree = [{ head: 0, l: 1 }];
  let current = 1; // 현재 입력될 숫자를 의미

  // n 부터 end 만큼 반복하면서 이진트리 생성 num 현재 노드를 의미
  // tree 배열의 주소 index 와 노드의 값이 같아 index 값이 즉 index 값을 가진 노드를 의미한다.
  for (let num = n; current < end; num++) {
    tree.push({
      root: num,
      l: current < end ? ++current : null,
      r: current < end ? ++current : null,
    });
  }

  // 전위 순회
  function front(obj) {
    // 노드가 채워지 있지 않은 경우 최상위 노드 1 정답 문자열에 추가
    if (obj.head) answer += obj.l;
    console.log("# root", obj);

    // 왼쪽 노드를 정답 문자열에 추가
    answer += obj.l ? obj.l + " " : "";
    // 왼쪽 노드 존재한다면 왼쪽노드를 활용해 재귀적으로 함수 호출
    if (tree[obj.l]) {
      console.log("# l", tree[obj.l]);
      front(tree[obj.l]);
    }

    // 오른쪽 노드를 정답 문자열에 추가
    answer += obj.r ? obj.r + " " : "";
    // 오른쪽 노드 존재한다면 왼쪽노드를 활용해 재귀적으로 함수 호출
    if (tree[obj.r]) {
      console.log("# r", tree[obj.r]);
      front(tree[obj.r]);
    }
  }

  // 후위 순회
  function back(obj) {
    // 노드가 채워지 있지 않은 경우 최상위 노드 1 정답 문자열에 추가
    if (obj.head) answer += obj.l;
    console.log("# root", obj);

    // 왼쪽 노드를 정답 문자열에 추가
    if (tree[obj.l]) {
      console.log("# l", tree[obj.l]);
      back(tree[obj.l]);
    }
    // 왼쪽 노드 존재한다면 왼쪽노드를 활용해 재귀적으로 함수 호출
    answer += obj.l ? obj.l + " " : "";

    // 오른쪽 노드 존재한다면 왼쪽노드를 활용해 재귀적으로 함수 호출
    if (tree[obj.r]) {
      console.log("# r", tree[obj.r]);
      back(tree[obj.r]);
    }
    // 오른쪽 노드를 정답 문자열에 추가
    answer += obj.r ? obj.r + " " : "";
  }

  console.log(tree);
  front(tree[0]);
  // back(tree[0]);
  return answer;
}
console.log(solution(1, 7));

트리를 구성하는 반복문이 current < end 까지 진행되므로 실질적으로 맨 마지막 노드 4,5,6,7 은 노드로 구성되지 않는다 즉 2와 3의 자식 노드로만 존재하게 된 상황이다.

이후 순회시에 마지막 노드들 4,5,6,7 노드를 방문하지 않고 값을 정답 문자열 집어넣기 위해 그 부모 노드에서 자식노드를 집어넣는 방식을 택하다보니 중위순회를 구현하기에도 어렵고(위와 같은 로직으로 구현하는데 실패하고 전위, 후위 순회만 구현함) head 노드를 따로 만들어 최상위 노드 1 을 집어 넣는 if 문으로 제작하는 등 만드는 동안에도 이상하다고 느낌

다른 코드를 참고해보고 생각해보니 결국 자식 노드의 값을 정답 문자열에 집어넣고 재귀함수를 사용하는 방식이 아니라
이 아닌 현재 노드의 값을 정답 문자열에 넣고 자식 노드값을 재귀함수에 넣어 처리하는 방식이 적절해 보였다.

위 방식을 적용하기 위해 최하위 노드 4,5,6,7 도 만들어 tree 배열에 노드 객체로 존재해야 가능하기 때문에 트리를 구성하는 반복문이 current < end 기준을 num < end 로 변경해 모든 노드를 객체로 만든 후 위 방식을 적용해 순회하는 함수를 구현하여 조금 더 깔끔하게 변경

다른 해결 방법

function solution(n, end) {
  let answer = "";
  function DFS(v) {
    if (v > end) return;
    else {
      // 전위순회
      answer += v + " ";
      DFS(v * 2);
      DFS(v * 2 + 1);

      // 중위순회
      // DFS(v * 2);
      // answer += v + " ";
      // DFS(v * 2 + 1);

      // 후위순회
      // DFS(v * 2);
      // DFS(v * 2 + 1);
      // answer += v + " ";
    }
  }
  DFS(n);
  return answer;
}
console.log(solution(1, 7));

풀이

1. 그림과 같이 왼쪽 자식 노드가 부모 노드의 x 2 이고 오른쪽 자식 노드가 부모 노드의 x 2 + 1 인 것을 활용
2. end 7 보다 커질 때 종료되는 재귀함수를 구현
   전위 순회 :
   1. 현재 노드의 값을 정답 문자열에 추가
   2. 재귀 함수에 현재 좌측 노드값을 의미하는 (노드값 x 2) 으로 다시 함수 호출
   3. 재귀 함수에 현재 우측 노드값을 의미하는 (노드값 x 2 + 1) 으로 다시 함수 호출
   중위 순회 :
   1. 재귀 함수에 현재 좌측 노드값을 의미하는 (노드값 x 2) 으로 다시 함수 호출
   2. 현재 노드의 값을 정답 문자열에 추가
   3. 재귀 함수에 현재 우측 노드값을 의미하는 (노드값 x 2 + 1) 으로 다시 함수 호출
   후위 순회 :
   1. 재귀 함수에 현재 좌측 노드값을 의미하는 (노드값 x 2) 으로 다시 함수 호출
   2. 재귀 함수에 현재 우측 노드값을 의미하는 (노드값 x 2 + 1) 으로 다시 함수 호출
   3. 현재 노드의 값을 정답 문자열에 추가

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard