LeetCode 105: TreeNodeを使用した二分木の構築

まず、問題の背景を理解しましょう。二分木は、各ノードが最大で2つの子ノードを持つデータ構造です。先行順序とは、ルートノードを最初に訪れ、その後に左部分木を訪れ、最後に右部分木を訪れる順序です。一方、中間順序とは、左部分木を訪れた後にルートノードを訪れ、その後に右部分木を訪れる順序です。

1. ルートノードを先行順序の最初の要素として識別します。
2. 中間順序でのルートノードの位置を見つけます。この位置によって、左部分木と右部分木の要素を識別できます。
3. 先行順序と中間順序のそれぞれについて、左部分木と右部分木の遍歴を取得します。
4. 左部分木と右部分木に対して再帰的に同じ手順を繰り返します。
5. 再帰を終了する条件は、先行順序または中間順序の遍歴が空である場合です。

このアプローチに基づいて、以下に示すようなPythonのコード例を提供します。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    root_index = inorder.index(root_val)
    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index + 1:]
    left_preorder = preorder[1:1 + len(left_inorder)]
    right_preorder = preorder[1 + len(left_inorder):]
    root.left = buildTree(left_preorder, left_inorder)
    root.right = buildTree(right_preorder, right_inorder)
    return root

上記のコードでは、TreeNodeクラスを定義し、buildTree関数を使用して二分木を再構築します。再帰的なアプローチを使用しており、与えられた先行順序と中間順序の遍歴から元の二分木を再帰的に構築します。

この投稿を通じて、LeetCodeの問題105についての理解を深め、二分木の再構築に関するアルゴリズムとコードの実装方法を学ぶことができるでしょう。