<Algorithm> 117. 중위순회(SWExpert)

1. 중위순회(SWExpert)

• 재귀를 이용한 트리 기본 순회문제

• 오랜만에 트리문제를 풀어보니 선뜻 생각이 나지않아 당황했지만 금방 풀 수 있었다.

• 첫 제출할때 fail 났는데 이유가 res의 chatAt으로 했는데 테스트케이스를 보니 10자리가 넘어가는 Node가 있었다. -> Token으로 대체함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
    public class Solution {
        static String res;
        static char[] alp;
        public static void main(String[] args) throws IOException {
            
            StringBuilder sb = new StringBuilder("");
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            for(int t = 0; t<10;t++) {
                int N = Integer.parseInt(br.readLine());
                Node[] tree = new Node[N+1];
                res = "";
                alp = new char[N + 1];
                /******************************
                 * 재귀를 활용해 L Root R 순서로 탐색 후
                 * 출력한다.
                 *******************************/
 
                for (int i = 1; i < N + 1; i++) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    int idx = Integer.parseInt(st.nextToken());
                    alp[idx] = st.nextToken().charAt(0);
                    tree[i] = new Node(idx);
                    if (st.hasMoreElements()) {
                        tree[i].left = Integer.parseInt(st.nextToken());
                    }
                    if (st.hasMoreElements()) {
                        tree[i].right = Integer.parseInt(st.nextToken());
                    }
                }
                int root = 1;
                inorder(tree, root);
                String result_inorder="";
                StringTokenizer st = new StringTokenizer(res);
                while (st.hasMoreTokens()){
                    result_inorder += alp[Integer.parseInt(st.nextToken())];
                }
 
                sb.append("#"+(t+1)+" "+result_inorder+"\n");
            }
            System.out.println(sb.toString());
        }
        public static void inorder(Node[] tree, int idx){
 
            if(tree[idx].left!=0) inorder(tree,tree[idx].left);
            res += tree[idx].v+" ";
            if(tree[idx].right!=0) inorder(tree,tree[idx].right);
 
        }
 
        static class Node{
            int v;
            int left = 0;
            int right = 0;
 
            public Node(int v) {
                this.v = v;
            }
        }
}
 

참고 & 출처