【AOJ解説(python)】ALDS1_7_D 先行/中間順巡回から後行順巡回を求める
本記事ではAizu Online Judgeより、ALDS1_7_Dの考え方と実際の解答をpythonで解説します。問題のリンク先は下記となります。
方針
ALDS1_7_Dの問題は、先行順巡回と中間順巡回で得られる節点の列から全体の二分木が構築できるという点に気づけるかがポイントになります。
全体の二分木が出来上がったら、あとはその木に対して後行順巡回の節点の列を求めて完了です。
先行順巡回と中間順巡回から全体の二分木を構築する手順
では、先行順巡回・中間順巡回の節点の列からどのように全体の二分木を構築していけばよいのでしょうか。
まず先行順巡回から調べてみます。
先行順巡回の特徴
先行順巡回(preorder)は、現在のノード→左の部分木→右の部分木の順でノードを訪問する巡回です。
ここで、先行順巡回の節点の列の先頭は必ず親ノードになるという特徴があります。
例えば、図の二分木における先行順巡回の節点の列はpreorder=5, 2, 4, 3, 1となります。
preorderの1番目の節点である5は、実際に二分木の親ノードになっています。
後行順巡回の特徴
一方、中間順巡回(inorder)は左の部分木→現在のノード→右の部分木の順で巡回します。
上図の二分木においては、中間順巡回の節点の列はinorder=4, 2, 3, 5, 1となります。
ここで、中間順巡回の節点の列は親ノードを境目にして左部分木と右部分木に分ける事が出来る点に着目します。
図の二分木を用いて、実際に確かめてみます。
中間順巡回の節点の列はinorder=4, 2, 3, 5, 1です。
親ノードは5なので、5を境目にして列を分割するとinrder=[4, 2, 3], 5, [1]となります。
この時、左の[]は左部分木 / 右の[]は右部分木をそれぞれ示しています。
つまり、親ノードが分かれば、中間順巡回の節点の列から下記のことが推測出来るという事になります。
例：inorder=4, 2, 3, 5, 1で親ノードが5であることが分かっている場合
親ノード・左部分木・右部分木に分割した後の処理
さらに、中間順巡回の節点の列を親ノードを境目にして左部分木と右部分木に分けた後を見てみます。
inrder=[4, 2, 3], 5, [1]の列から、5を親ノードとした左部分木[4, 2, 3]・右部分木[1]が判明していますが、左部分木の詳細は分かりません。
ここで再度、先行順巡回の節点の列preorder=5, 2, 4, 3, 1を見てみます。
左部分木の[4, 2, 3]は、先行順巡回では2～4番目で[2, 4, 3]になっています。
この[2, 4, 3]は左部分木に対して先行順巡回を行った結果と捉えられるので、先述の通り先行順巡回の1番目である2が左部分木の親ノードという事が分かります。
親ノードが判明したら、再度中間順巡回の列[4, 2, 3]より、部分木を親ノードを境目として左部分木と右部分木に分ける事が出来ます。
今回は2が親ノードであるため、inorder=[[4], 2, [3]]と分割できます。
このようにして、先行順巡回および中間順巡回から全体の二分木が構築出来ました。
手順をまとめると、以下となります。
１．先行順巡回の節点の列の先頭から親ノードを導出
２．中間順順巡回の節点の列より、親ノードを境目にして左部分木と右部分木に分割
３．分割後の左部分木・右部分木に該当する箇所を先行順巡回の節点の列から抽出
４．上記1～3の手順を再帰的に繰り返す
実装
方針で定めた手順を、Pythonで実現するにはどのように実装すればよいか考えていきます。
手順１・２の実装
手順１:先行順巡回の節点の列の先頭から親ノードを導出
手順２:中間順順巡回の節点の列より、親ノードを境目にして左部分木と右部分木に分割
については、下記コードにて実現可能です。
build_tree関数を定義して、引数にpreorder(先行順巡回の節点の列)とinorder(中間順巡回の節点の列)を取っています。
class Node:
def __init__(self, key: int) -> None:
self.key = key
self.left = None
self.right = None
def build_tree(preorder:list, inorder:list) -> Node:
# 手順１：親ノードをpreorderの最初の要素から取得
root = Node(preorder[0])
# 手順２：親ノードのindex番号を取得して、左部分木と右部分木に分割
index = inorder.index(root.key)
left_subtree = inorder[:index]
right_subtree = inorder[index + 1:]
手順３の実装
手順3と4の実装が山となります。
最初に手順3の実装から考えていきます。
手順３．分割後の左部分木・右部分木に該当する箇所を先行順巡回の節点の列から抽出
上記手順は、方針内の下記箇所に該当します。
さらに、中間順巡回の節点の列を親ノードを境目にして左部分木と右部分木に分けた後を見てみます。
inrder=[4, 2, 3], 5, [1]の列から、5を親ノードとした左部分木[4, 2, 3]・右部分木[1]が判明していますが、左部分木の詳細は分かりません。
ここで再度、先行順巡回の節点の列preorder=5, 2, 4, 3, 1を見てみます。
左部分木の[4, 2, 3]は、先行順巡回では2～4番目で[2, 4, 3]になっています。
すなわち、「inorderの左部分木=[4, 2, 3]はpreorderで2～4番目である」という事をどのように導出すればよいかを考えます。
まず、preorderの1番目は必ず親ノードになるため、左部分木はpreorderの2番目の要素からとなります。
次に、inrder=[4, 2, 3], 5, [1]内の親ノード5の手前のノード、つまりノード3に着目します。
このノード3はinorder内で3番目の要素となりますが、3番目よりも手前のノードはすべて左部分木のノードとなるので左部分木の全ノード数は3つです。
したがって、親ノード手前にあるノードの要素番号と左部分木のノード数が一致するという事が分かります。
左部分木はpreorderの2番目の要素からという事と、左部分木の全ノード数は3つという事が分かれば、preorderの2,3,4番目のノードは左部分木であるという事が導出されます。
※右部分木については補集合の考え方で導出します。
上記を踏まえ、Pythonのコードに落とし込んでいきます。
def build_tree(preorder:list, inorder:list) -> Node:
# 手順１：親ノードをpreorderの最初の要素から取得
root = Node(preorder[0])
# 手順２：親ノードのindex番号を取得して、左部分木と右部分木に分割
index = inorder.index(root.key)
left_subtree_inorder = inorder[:index]
right_subtree_inorder = inorder[index + 1:]
# 手順３：分割後の左部分木・右部分木に該当する箇所を先行順巡回の節点の列から抽出
# inorder内における親ノード手前のノードの要素番号：index (0-indexedのため-1不要)
# 左部分木は2番目の要素からindex分までが該当 (0-indexedのため始点は1)
left_subtree_preorder = preorder[1:index + 1]
# 右部分木は残りの要素
right_subtree_preorder = preorder[index + 1:]
手順４の実装
最後に、手順4の実装について考えます。
４．上記1～3の手順を再帰的に繰り返す
考え方としては、build_tree関数で親ノード・左部分木・右部分木を抽出し、抽出した各部分木に対しても再度build_tree関数を適用させるという方針となります。
すなわち、build_tree(preorder, inorder)の引数を部分木に変えて
build_tree(left_subtree_preorder, left_subtree_inorder)
build_tree(right_subtree_preorder, right_subtree_inorder)
と再帰的に呼び出すことにより実装します。
終端の条件は部分木に子ノードが存在しなくなった時です。また、戻り値は部分木の親ノードとします。すなわち、親ノードから左部分木・右部分木のどちらも見つからなかった場合、その親ノードを戻り値として返して一つ前の再帰呼び出しに戻ります。
pythonのコードで示すと以下のようになります。引数の箇所はleft_subtree_preorderのような変数を用いず、そのままpreorder[1:index + 1]のように記載しています。
def build_tree(preorder:list, inorder:list) -> Node:
if inorder:
# ルートはpreorderの最初の要素
root = Node(preorder[0])
# ルートの位置をinorder内で見つける
index = inorder.index(root.key)
# 左部分木と右部分木を再帰的に構築
root.left = build_tree(preorder[1:index + 1], inorder[:index])
root.right = build_tree(preorder[index + 1:], inorder[index + 1:])
return root
return None
解答例
最終的な解答例は以下の通りです。
build_tree関数で先行順巡回と中間順巡回で得られる節点の列から全体の二分木が構築し、post_order関数にて後行順巡回の接点の列を求めています。
class Node:
def __init__(self, key: int) -> None:
self.key = key
self.left = None
self.right = None
def build_tree(preorder:list, inorder:list) -> Node:
if inorder:
# ルートはpreorderの最初の要素
root = Node(preorder[0])
# ルートの位置をinorder内で見つける
index = inorder.index(root.key)
# 左部分木と右部分木を再帰的に構築
root.left = build_tree(preorder[1:index + 1], inorder[:index])
root.right = build_tree(preorder[index + 1:], inorder[index + 1:])
return root
return None
def post_order(node: Node) -> None:
def _post_order(node: Node) -> None:
if node is not None:
_post_order(node.left)
_post_order(node.right)
output.append(str(node.key))
output = []
_post_order(node)
print(' '.join(output))
m = int(input())
preorder_list = list(map(int, input().split()))
inorder_list = list(map(int, input().split()))
root = build_tree(preorder_list, inorder_list)
post_order(root)
参考
Discussion