Help us understand the problem. What is going on with this article?

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

概要

二分木の深さ優先探索(DFS)には先行順巡回:pre-order, 中間順巡回:in-order, 後行順巡回:post-orderの3通りの方法がありますが、そのうち中間順巡回と先行(後行)順巡回の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)
Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away