Construct Binary Tree
from Preorder & Inorder Traversal

アルゴリズム概要

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

preorder = [-1]
inorder  = [-1]

ステップバイステップ解説

Python 実装

import sys
from typing import Optional

sys.setrecursionlimit(10_000)  # 偏った木(n=3000)の深い再帰に備えて上限を緩和


class TreeNode:
    __slots__ = ("val", "left", "right")
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right


class Solution:
    def buildTree(
        self,
        preorder: list[int],
        inorder:  list[int],
    ) -> Optional[TreeNode]:
        """
        preorder（前順）と inorder（中順）から二分木を復元する。
        Time:  O(n) - 各ノードをちょうど1回処理
        Space: O(n) - dict(n エントリ) + 再帰スタック(高さ h)
        """
        # ① 型チェック: list 以外が渡された場合に分かりやすいエラーを出す
        if not isinstance(preorder, list) or not isinstance(inorder, list):
            raise TypeError("Both preorder and inorder must be lists")

        # ② 長さ不一致チェック: 同じ木でなければ復元不可
        if len(preorder) != len(inorder):
            raise ValueError(
                f"Length mismatch: preorder={len(preorder)}, inorder={len(inorder)}"
            )

        # ③ 空リストチェック: ノード0個 → Noneを返す
        if not preorder:
            return None

        n = len(inorder)

        # ④ 前処理: inorder の「値→インデックス」を dict 内包表記で O(n) 構築
        #    ★毎回 list.index() を使うと全体 O(n²) → dict なら O(1) ルックアップ
        inorder_index: dict[int, int] = {val: i for i, val in enumerate(inorder)}

        # ⑤ preorder を先頭から消費するカーソル
        #    int はイミュータブル(変更不可)なので nonlocal で外側変数を共有する
        preorder_idx: int = 0

        def build(lo: int, hi: int) -> Optional[TreeNode]:
            """inorder の [lo, hi] 範囲に対応する部分木を再帰構築する"""
            nonlocal preorder_idx

            # ⑥ 再帰の終了条件: 範囲が空(lo > hi) → 部分木なし
            if lo > hi:
                return None

            # ⑦ preorder の現在位置 = この部分木のルート値
            #    preorder は「ルート→左→右」順なので呼ばれた時点の先頭が必ずルート
            root_val: int = preorder[preorder_idx]
            preorder_idx += 1  # 次の再帰のためにカーソルを進める

            # ⑧ dict でルートの inorder 上の位置を O(1) で取得
            #    この位置(mid)が左部分木と右部分木の境界線になる
            mid: int = inorder_index[root_val]

            # ⑨ ノードを生成し左→右の順で再帰構築して接続する
            #    ★左を先にする理由: preorder が「ルート→左→右」順のため
            #    左の再帰が終わると次のカーソル位置が右部分木のルートになる
            node = TreeNode(root_val)
            node.left  = build(lo,      mid - 1)  # 左部分木(mid の左側)
            node.right = build(mid + 1, hi)        # 右部分木(mid の右側)
            return node

        # ⑩ inorder 全体(0〜n-1)を対象に木全体を構築して返す
        return build(0, n - 1)

前処理: inorder_index = {9:0, 3:1, 15:2, 20:3, 7:4}
preorder_idx = 0

build(0, 4):
  root_val=3 (preorder[0]), preorder_idx→1, mid=inorder_index[3]=1
  node = TreeNode(3)
  node.left  = build(0, 0)
    root_val=9, preorder_idx→2, mid=0
    node.left  = build(0,-1) → lo>hi → None
    node.right = build(1, 0) → lo>hi → None
    ✅ return TreeNode(9)
  node.right = build(2, 4)
    root_val=20, preorder_idx→3, mid=3
    node.left  = build(2, 2)
      root_val=15, preorder_idx→4, mid=2
      → TreeNode(15, None, None)  ✅
    node.right = build(4, 4)
      root_val=7, preorder_idx→5, mid=4
      → TreeNode(7, None, None)   ✅
    ✅ return TreeNode(20, left=15, right=7)
✅ return TreeNode(3, left=9, right=20)

最終ツリー:
        3
       / \
      9  20
         / \
        15   7
Output: [3,9,20,null,null,15,7]  ✅

処理フローチャート

フローの説明：
入口の検証（①②③）でエラーを早期発見し、dict 前処理（③）で O(n²) を O(n) に改善します。再帰 build(lo,hi) では終了条件 lo>hi を確認した後、preorder カーソルからルートを取得（⑤）し、dict でルートの inorder 位置を特定（⑥）して左→右の順に再帰呼び出しを行います（⑦⑧）。各再帰は必ず処理対象範囲が縮小するため有限回で終了します。

計算量分析

⏱ 時間計算量

💾 空間計算量

⚖ アプローチ比較

📖 用語集

このページで登場した専門用語をまとめました。分からない言葉が出てきたとき参照してください。