149. 이진 검색 트리

백준

1. Python

import sys

# default 값이 1000이다
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def post_order(start, end):
    # 역전시 리턴
    if start > end:
        return

    # 루트 노드
    root = pre_order[start]
    idx = start + 1

    # root보다 커지는 지점을 찾는 과정  
    # for문으로 찾으면 안된다. 아래서 설명  
    while idx <= end:
        if pre_order[idx] > root:
            break
        idx += 1

    # 왼쪽 서브트리
    post_order(start + 1, idx - 1)

    # 오른쪽 서브트리
    post_order(idx, end)

    # 후위순회이므로 제일 마지막에 찍으면 된다
    print(root)


pre_order = []
while 1:
    try:
        pre_order.append(int(input()))
    # try에서 예외 발생시 break 실행
    except:
        break

post_order(0, len(pre_order) - 1)

2. Java

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

public class Main {
    // file???
    // cpp cin.eof() == true
    // while (cin >> preorder[i++]);

    // scanf("%d", &a) == -1 끝
    // freopen("res/test.in", "r", stdin);
    private static int[] a = new int[10000];
    private static int sz;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("src/test.in"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = br.readLine()) != null) {
            a[sz] = Integer.parseInt(str.trim());
            sz++;
        }
        recur(0, sz - 1);
    }

    private static void recur(int s, int e) {
        // a[s] == 전위 순회에서는 root
        if (s == e) {
            System.out.println(a[s]);
            return;
        }
        else if (s > e) {
            return;
        }       
        else {
            int where = s + 1;
            while (where <= e) {
                if (a[where] > a[s]) break;
                else where++;
            }
            // left
            recur(s + 1, where - 1);
            // right
            recur(where, e);
            System.out.println(a[s]);
        }
    }
}