まず、バイナリツリーの再構築にはいくつかのアルゴリズムがあります。以下にいくつかの一般的なアプローチを示します。
- 再帰的なアプローチ: このアプローチでは、再帰関数を使用してツリーを再構築します。まず、Levelorder配列からルートノードを取得し、そのノードがInorder配列のどの位置にあるかを見つけます。それに基づいて、Inorder配列を左部分木と右部分木に分割します。再帰的にこれを繰り返し、各部分木に対して同じ手順を適用します。以下に再帰的なアプローチのコード例を示します。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(levelorder, inorder):
if not levelorder or not inorder:
return None
root_val = levelorder[0]
root = TreeNode(root_val)
root_index = inorder.index(root_val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index + 1:]
left_levelorder = [val for val in levelorder if val in left_inorder]
right_levelorder = [val for val in levelorder if val in right_inorder]
root.left = buildTree(left_levelorder, left_inorder)
root.right = buildTree(right_levelorder, right_inorder)
return root
levelorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
tree = buildTree(levelorder, inorder)- スタックを使用したイテレーティブなアプローチ: このアプローチでは、スタックを使用してツリーを再構築します。Levelorder配列からルートノードを取得し、そのノードを作成します。次に、Inorder配列の要素を順番に処理しながら、スタックを使用してツリーを再構築していきます。以下にイテレーティブなアプローチのコード例を示します。
def buildTree(levelorder, inorder):
if not levelorder or not inorder:
return None
root_val = levelorder.pop(0)
root = TreeNode(root_val)
stack = [root]
while levelorder:
curr_val = levelorder.pop(0)
curr_node = stack[-1]
if curr_node.val != inorder[0]:
curr_node.left = TreeNode(curr_val)
stack.append(curr_node.left)
else:
while stack and stack[-1].val == inorder[0]:
curr_node = stack.pop()
inorder.pop(0)
curr_node.right = TreeNode(curr_val)
stack.append(curr_node.right)
return root
levelorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
tree = buildTree(levelorder, inorder)これらはバイナリツリーを再構築するための一般的な方法のいくつかです。再構築アルゴリズムは、与えられた入力によって異なる結果をもたらすことがあります。したがって、それぞれのアプローチの利点と欠点を理解し、問題に応じて適切な方法を選択する必要があります。また、再構築されたバイナリツリーを適切に出力するために、適切なデータ構造やヘルパー関数を使用することも重要です。
この記事では、バイナリツリーの再構築に関する基本的な情報と、再帰的なアプローチとイテレーティブなアプローチのコード例を提供しました。これにより、読者は問題を理解し、実装するための手助けができるでしょう。