ALDS1_7_D: Reconstruction of the Tree (続き)

二分木をpreorderで巡回した結果とinorderので巡回した結果を入力として受け取り、 その二分木をpostorderで巡回したときの結果を出力せよ

ALDS1_7_D: Reconstruction of the Tree - kb84tkhrのブログ

 これ考えてみる

ということはもっと狙いを絞ってつくらないといけないのか わかりやすいところではinorderの最初の要素が左端に来るとかあるので なにかやれそうではある

思いついた気がする

preorderで先頭にある要素は根だから場所が確定してる
1 2 3 4 5であれば1が根
2はどっちにあるかはinorderを見ればわかる
3 2 4 1 5で2は1より左にあるから根の左にあるはず

preorderの先頭の要素aを根に置く
inorderをaで左右に分割する
preorderを上記の分割にそって分割する
分割したそれぞれについて同様に実施して、根の左と右にくっつける

これでいけんじゃね

class Node:
    def __init__(self, val, left, right):
        self.val = val
        self.left = left
        self.right = right

    def __iter__(self):
        yield from self.postorder()

    def postorder(self):
        yield from self.left
        yield from self.right
        yield self

def reconstruct(preorder, inorder):
    if len(preorder) == 0:
        return []

    root_val = preorder[0]
    root_index = inorder.index(root_val)
    inorder_left = inorder[:root_index]
    inorder_right = inorder[root_index + 1 :]
    preorder_left = [x for x in preorder if x in inorder_left]
    preorder_right = [x for x in preorder if x in inorder_right]

    return Node(
        root_val,
        reconstruct(preorder_left, inorder_left),
        reconstruct(preorder_right, inorder_right),
    )

def main():
    n = int(input())
    preorder = [int(x) for x in input().split()]
    inorder = [int(x) for x in input().split()]

    print(*[node.val for node in reconstruct(preorder, inorder).postorder()])

main()

いけた

解説・サンプルコードを読む
考え方は同じだけど処理対象・左・右のインデックスを使って配列をコピーしないでやってる
pre++がちょっと気になったけど
結局処理対象は単純に左からひとつずつ進むだけなのか
再帰にグローバル変数が関係してくるとイメージが難しい
やらずに済むならやらずに済ませたい