📝문제

노드 클래스를 만들어 트리를 구현하고 순회 방법에 따라 방문하는 순서대로 노드를 출력하는 문제
재귀 알고리즘으로 왼쪽 자식 노드 방문, 오른쪽 자식 노드 방문을 적절히 순서대로 작성하면 된다.

• preorder의 경우 : root -> left -> right 이므로, 방문한 노드를 기록한 후 왼쪽 자식 노드로 이동하고 리턴되어 오른쪽 자식 노드로 이동하도록 한다.
• inorder의 경우 : left -> root -> right 이므로, 왼쪽 자식 노드로 계속 이동하다가 다음으로 이동할 노드가 없으면 리턴하여 자신의 노드를 기록하고, 오른쪽 노드로 이동한다.
• postorder의 경우 : left -> right -> root 이므로, 왼쪽 자식 노드로 계속 이동한 다음, 왼쪽 자식 노드가 없을 경우 오른쪽 자식 노드로 이동하게 한다. 그다음 리턴되어 자신의 노드를 기록한다.

📌코드

package DataStructure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ1991 {

  // 노드 클래스
  static class Node{
    int left, right; //왼쪽자식, 오른쪽자식

    public Node(int left, int right){
      this.left = left;
      this.right = right;
    }
  }

  static int n;
  static List<Node>[] tree; // 노드 간의 연결관계를 알기 위해 list형의 배열 생성
  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    // init tree
    tree = new List[n];
    for(int i = 0; i < tree.length; i++){
      tree[i] = new ArrayList<>();
    }
    StringTokenizer st;
    // add node
    for(int i = 0; i < n; i++){
      st = new StringTokenizer(br.readLine());
      // change to integer ('.' - 'A' == -19)
      int p = st.nextToken().charAt(0) - 'A';
      int l = st.nextToken().charAt(0) - 'A';
      int r = st.nextToken().charAt(0) - 'A';
      tree[p].add(new Node(l, r));
    }
    // preorder
    preorder(0);
    sb.append("\n");
    // inorder
    inorder(0);
    sb.append("\n");
    //postorder
    postorder(0);
    System.out.println(sb.toString());
  }
  static void preorder(int start){
    // case : .
    if(start < 0) return;

    // 자식노드가 없으면 리턴
    if(tree[start].isEmpty()) return;

    // root -> left -> right
    sb.append((char) ('A'+start));
    preorder(tree[start].get(0).left);
    preorder(tree[start].get(0).right);
  }
  static void inorder(int start){
    // case : .
    if(start < 0) return;
    // have no child
    if(tree[start].isEmpty()) return;
    // left -> root -> right
    inorder(tree[start].get(0).left);
    sb.append((char) ('A' + start));
    inorder(tree[start].get(0).right);
  }
  static void postorder(int start){
    // case : .
    if(start < 0) return;
    // have no child
    if(tree[start].isEmpty()) return;
    // left -> root -> right
    postorder(tree[start].get(0).left);
    postorder(tree[start].get(0).right);
    sb.append((char) ('A' + start));
  }
}