코딩 테스트 합격자 되기 | 문제25. 트리 순회

25. 트리순회

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

제약조건

입력 노드값의 개수는 1개 이상 1000개 이하이다

노드값은 정수형이며, 중복되지 않는다.

 

입출력의 예

nodes	return
[1,2,3,4,5,6.7]	["1 2 4 5 3 6 7","4 2 5 1 6 3 7","4 5 2 6 7 3 1"]

 

내 답안

import java.util.*;

 class Solution {
     public static void main(String[] args) {
         int[] nodes = {1, 2, 3, 4, 5, 6, 7};
         String[] result = solution(nodes);
     }

     public static String[] solution(int[] nodes) {
         String[] arr = new String[3];
         arr[0] = preOrder(nodes, 0);
         arr[1] = inOrder(nodes, 0);
         arr[2] = postOrder(nodes, 0);
         return arr;
     }

     public static String preOrder(int[] nodes, int idx) {
         if(idx>=nodes.length){
             return "";
         }
         StringBuilder sb = new StringBuilder();
         String left = preOrder(nodes,idx*2+1);
         String right = preOrder(nodes,idx*2+2);
         sb.append(nodes[idx]+" ");
         sb.append(left);
         sb.append(right);
         return sb.toString();
     }

     public static String inOrder(int[] nodes, int idx) {
         if(idx>=nodes.length){
             return "";
         }
         StringBuilder sb= new StringBuilder();
         String left = inOrder(nodes,idx*2+1);
         String right = inOrder(nodes,idx*2+2);

         sb.append(left);
         sb.append(nodes[idx]+" ");
         sb.append(right);
         return sb.toString();
     }

     public static String postOrder(int[] nodes, int idx) {
         if(idx>=nodes.length){
             return "";
         }
         StringBuilder sb = new StringBuilder();
         String left = postOrder(nodes,idx*2+1);
         String right = postOrder(nodes,idx*2+2);
         sb.append(left);
         sb.append(right);
         sb.append(nodes[idx]+" ");
         return sb.toString();
     }

 }

//           1               0
//         2    3          1    2
//      4   5  6  7      3   4 5  6
//전위  123 
//중위  213
//후위  231
//
//0 =0
//1 = 0*2 +1
//2 = 0*2 +2
//3 = 1*2 +1
//왼쪽 = root * 2 + 1
//오른쪽 = root * 2 + 2