🥚質問する

https://www.acmicpc.net/problem/5639

グラフィック理論

グラフィックナビゲーション

ツリー

在貴

🥚入力/出力

🍳コード#コード#

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def pre_to_post(start, end):
    if start > end:
        return
    
    root = preorder[start]

    # root보다 커지는 인덱스 찾기
    idx = start
    while idx <= end:
        if preorder[idx] > root:
            break
        idx += 1
    
    # 왼쪽
    pre_to_post(start+1, idx-1)
    # 오른쪽
    pre_to_post(idx, end)
    # 루트
    print(root)


# 입력
preorder = []
while True:
    try:
        preorder.append(int(input()))
    except:
        # EOF -> break
        break

# pre_to_post
pre_to_post(0, len(preorder)-1)

🧂アイデア

グラフィック理論

入力の受信😮

題の入力では,ノードの個数や入力終了条件は与えられていない.

EOFを入力する場合は終了する必要があります.

したがって,while loop内部try-exception文を用いて,EOF時に入力されるループを構成する.

# 입력
preorder = []
while True:
    try:
        preorder.append(int(input()))
    except:
        # EOF -> break
        break

ぜんれつ巡り

前列は「ルート-左-右」の順で、バイナリ検索ツリーを順に巡回します.

このとき、バイナリ検索ツリーでは、左側がルートより小さいノードであり、右側がルートより大きいノードである.したがって、入力50302452228458985260は、以下のように分けられる.
50 | 30 24 5 28 45 | 98 52 60

次の図に示すように、この手順

を繰り返します.

「左処理->右処理->ルート出力」動作を再帰的に繰り返すと、次のサイクルの結果が得られます.

このとき、ルートより大きい数字のインデックスが初めて発見された場合、そのインデックスに基づいて左、右を区別することができます.

def pre_to_post(start, end):
    if start > end:
        return
    
    root = preorder[start]

    # root보다 커지는 인덱스 찾기
    idx = start
    while idx <= end:
        if preorder[idx] > root:
            break
        idx += 1
    
    # 왼쪽
    pre_to_post(start+1, idx-1)
    # 오른쪽
    pre_to_post(idx, end)
    # 루트
    print(root)

タイムアウトコード

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def pre_to_post(preorder):
    global postorder
    if len(preorder) == 0:
        return

    root = preorder[0]

    left = []
    right = []

    for i in range(1, len(preorder)):
        if preorder[i] < root:
            left.append(preorder[i])
        else:
            right.append(preorder[i])
    pre_to_post(left)
    pre_to_post(right)
    postorder.append(root)



postorder = []
preorder = []
while True:
    try:
        preorder.append(int(input()))
    except:
        break

pre_to_post(preorder)
for x in postorder:
    print(x)

の上のコードは初めて試したコードですが、タイムアウトしました.

を通過するコードとの違いはpre to post関数の内部実装にある.

のコードによって右側の部分の開始インデックスを検索して中断します.
パスされていない上のコードではroot以外のすべての要素が巡回され、左、右というリストがそれぞれ作成され、要素が加わっているので時間がかかります.