木の巡回配列から二分木を生成する

概要

二分木の深さ優先探索(DFS)には先行順巡回：pre-order, 中間順巡回：in-order, 後行順巡回：post-orderの３通りの方法がありますが、そのうち中間順巡回と先行（後行）順巡回の2つの配列が与えられれば、対象となる二分木を生成することができます。本記事ではin-orderとpost-orderの配列から二分木を生成する方法を紹介します。

方針

まず、pre-orderの場合は先頭の要素、post-orderの場合は最後尾の要素がrootになることに着目します。また、in-orderの配列をrootの要素の位置で分割した場合、左側の部分配列はrootの左の部分木、右側の部分配列はrootの右の部分木のそれぞれのin-orderになります。そこで下記の手順を再帰的に繰り返すことで、二分木を生成することができます。

1. post-orderの配列の最後尾をrootの値として取り出す
2. in-orderの配列を、rootの値の位置を中心に分割する
3. 左右に分割したin-orderの配列と、最後尾を除いたpost-orderの配列からsub-treeを生成し、それぞれrootの子ノードにセットする

実装例

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def buildTree(self, inorder, postorder):
        # post-orderの最後尾をrootの値として取り出す
        rootVal = postorder.pop()

        # in-orderの配列を分割するため、rootValのindexを取得する
        rootIdx = inorder.index(rootVal)

        root = TreeNode(rootVal)

        # in-orderの配列をrootIdxを中心に分割し、左右の部分木を再帰的に生成する
        if len(postorder) > 0 and rootIdx < len(inorder) - 1:
            root.right = self.buildTree(inorder[rootIdx+1:], postorder)
        if len(postorder) > 0 and rootIdx > 0:
            root.left = self.buildTree(inorder[:rootIdx], postorder)

        return root

実行

# 下記のような二分木を生成する
#    3
#   / \
#  9  20
#    /  \
#   15   7

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

root = Solution().buildTree(inorder, postorder)