[Today I Learned 07] 2. 白駿(#2263)
ツリーツアーを習う過程で、中尉ツアーとバックツアーの価格を前衛ツアーに変える問題に遭遇した.木巡りには理解できたと思いますが、問題に直面して、どうすればいいか分かりません.だから私は答えを見て、理解の方法で書きたいです.
n個の頂点を持つバイナリツリーの頂点には、1からnまでの番号が重複していません.このバイナリ・ツリーのインベントリとインベントリが指定されている場合は、サブスクリプションを取得するプログラムを作成します.
第1行はn(1≦n≦100000)を与える.次の行はインボイスを表すn個の自然数を与え、次の行は同じように後注文を与える.
最初の行にサブスクリプションを出力します.
方法
1.後ろの巡回値の最後の数字は、ルート全体です.
2.中位数順が
3.見つかった左ノード数と右ノード数を用いて、中位数を
4.同様に後列を左、右、根に分けることができる.
5.上記の手順を繰り返します.
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)
Reference
この問題について([Today I Learned 07] 2. 白駿(#2263)), 我々は、より多くの情報をここで見つけました https://velog.io/@yunchanpark/Today-I-Learned-07-2.-백준2263テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol