문제

이해

이진 검색 트리는 부모 노드를 기준으로 왼쪽 서브 트리는 모두 부모 노드보다 작고 오른쪽 서브 트리는 모두 부모 노드보다 큰 트리이다.

이러한 이진 검색 트리를 전위 순회한 결과를 입력받아 후위 순회한 결과로 출력하라.

접근

문제는 2단계로 구성된다.

첫번째는 전위 순회한 입력값을 받아 트리를 구성하는 것, 두번째는 구성한 트리를 후위 순회로 출력하는 것.

트리 구성

첫번째 단계를 보자. 특정 노드 값을 입력받았을 때 위치를 특정하는 방법은 해당 값을 비교하는 것이다.

루트노드보다 작다면 왼쪽 서브트리로 크다면 오른쪽 서브트리로 가게 되는데 이후에는 서브트리에서 다시 값을 비교하면 된다. (이 때 값을 비교할 때 해당 서브트리의 루트를 기준으로 삼는다.)

즉, 루트를 타고 들어가 서브트리를 탐색하는.. 재귀를 활용해 노드를 삽입할 수 있는 것이다.

    void AddChild(int n) {
      if (n < this.num) {
        if (this.l_child == null) {
          this.l_child = new Node(n);
        } else
          this.l_child.AddChild(n);
      } else {
        if (this.r_child == null) {
          this.r_child = new Node(n);
        } else
          this.r_child.AddChild(n);
      }

위 코드는 Node 클래스의 AddChilde 메서드이다. 위처럼 현재 노드에 자식 노드를 삽입하려 할 때 빈 곳이라면 삽입, 아니라면 해당 서브트리로 재귀를 수행하면 된다.

후위 순회

이제는 후위 순회를 보자. 후위 순회는 왼쪽 - 오른쪽 - 루트 으로 순회하는 방식이다.

따라서, 이 역시도 루트를 기준으로 왼쪽 서브트리 후위순회 - 오른쪽 서브트리 후위순회 - 루트 처럼 재귀를 활용하여 순회할 수 있다.

  static void PostOrder(Node node) {
    if (node == null) {
      return;
    }
    PostOrder(node.l_child);
    PostOrder(node.r_child);
    System.out.println(node.num);
  }

위처럼 node가 비어있으면 return 하고 아니라면 해당 노드를 기준으로 왼, 우, 자신을 출력한다.

코드

package java_baekjoon;

import java.util.*;
import java.io.*;

public class prob5639 {
  static class Node {
    int num;
    Node l_child, r_child;

    Node(int num) {
      this.num = num;
    }

    Node(int num, Node l_child, Node r_child) {
      this.num = num;
      this.l_child = l_child;
      this.r_child = r_child;
    }

    void AddChild(int n) {
      if (n < this.num) {
        if (this.l_child == null) {
          this.l_child = new Node(n);
        } else
          this.l_child.AddChild(n);
      } else {
        if (this.r_child == null) {
          this.r_child = new Node(n);
        } else
          this.r_child.AddChild(n);
      }
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    Node root = new Node(Integer.parseInt(br.readLine()));

    while (true) {
      String input = br.readLine();

      if (input == null || input.equals("")) {
        break;
      }

      int node = Integer.parseInt(input);
      root.AddChild(node);
    }

    PostOrder(root);
  }

  static void PostOrder(Node node) {
    if (node == null) {
      return;
    }
    PostOrder(node.l_child);
    PostOrder(node.r_child);
    System.out.println(node.num);
  }
}

결과