[Today I Learned 07] 2. 白駿(#2263)

ツリーツアーを習う過程で、中尉ツアーとバックツアーの価格を前衛ツアーに変える問題に遭遇した.木巡りには理解できたと思いますが、問題に直面して、どうすればいいか分かりません.だから私は答えを見て、理解の方法で書きたいです.

1.巡视茨利(#2263)

質問する

n個の頂点を持つバイナリツリーの頂点には、1からnまでの番号が重複していません.このバイナリ・ツリーのインベントリとインベントリが指定されている場合は、サブスクリプションを取得するプログラムを作成します.

入力

第1行はn(1≦n≦100000)を与える.次の行はインボイスを表すn個の自然数を与え、次の行は同じように後注文を与える.

しゅつりょく

最初の行にサブスクリプションを出力します.
方法
1.後ろの巡回値の最後の数字は、ルート全体です.
2.中位数順が왼쪽, 루트, 오른쪽であるため、接尾辞順で見つかったルート値を用いて左ツリーと右ツリーのノード数を求めることができる.
3.見つかった左ノード数と右ノード数を用いて、中位数を왼쪽 트리, 루트, 오른쪽 트리に分割する.
4.同様に後列を左、右、根に分けることができる.
5.上記の手順を繰り返します.

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

# 노드 개수
n = int(input())
# 중위 순회 결과 값
inorder = list(map(int, input().split()))
# 후위 순회 결과 값
postorder = list(map(int, input().split()))
# 중위 순회 각 노드 인덱스 
index = [0] * (n + 1)
for i in range(n):
    index[inorder[i]] = i
    
# 전위 순회로 바꾸는 함수
def preorderset(inStart, inEnd, poStart, poEnd):
    if inStart > inEnd or poStart > poEnd: return
    
    # 트리의 루트
    root = postorder[poEnd]
    # 루트의 인덱스
    root_idx = index[root]
    # 전위 순회는 '루트-왼쪽-오른쪽'이기 때문에 바로 루트 출력
    print(root, end=' ')
    
    # 왼쪽 노드 개수
    left = root_idx - inStart
    # 오른쪽 노드 개수
    right = inEnd - root_idx
    
    # 왼쪽 트리 재귀
    preorderset(inStart, root_idx - 1, poStart, poStart + left - 1)
    # 오른쪽 트리 재귀
    preorderset(root_idx + 1, inEnd, poEnd - right, poEnd - 1)

preorderset(0, n - 1, 0, n - 1)