Construct Binary Tree from
Inorder and Postorder Traversal

アルゴリズム概要

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

      3
     / \
    9   20
       /  \
      15    7

なぜこれが正解か： postorderの末尾3がルート → inorderで3の左が[9]（左部分木）、右が[15,20,7]（右部分木）と特定できる。この操作を再帰的に繰り返すことで木全体を復元できる。

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

▶ Play ボタンで自動再生、Prev/Next で手動操作できます。

Python 実装

import sys
from typing import Optional, List

class Solution:
    def buildTree(
        self,
        inorder: List[int],
        postorder: List[int]
    ) -> Optional[TreeNode]:
        # Python のデフォルト再帰上限は 1000。
        # 完全偏り木では n=3000 段の再帰が必要になるため上限を引き上げる。
        sys.setrecursionlimit(10_000)

        # dict 内包表記で「値 → inorder のインデックス」を O(n) で1回だけ構築。
        # list.index() を毎回呼ぶと O(n²) になるため、事前構築で O(1) 検索を実現。
        idx_map: dict[int, int] = {v: i for i, v in enumerate(inorder)}

        # post_idx をリストで包む慣用句。
        # 内側関数から外側の int を書き換えるには nonlocal が必要だが、
        # リストに包むことで「リストの中身を変える」操作になり nonlocal 不要になる。
        post_idx: List[int] = [len(postorder) - 1]

        def dfs(left: int, right: int) -> Optional[TreeNode]:
            # 終了条件：左端が右端を超えた = この範囲に要素がない = 部分木なし
            if left > right:
                return None

            # postorder の末尾から現在の部分木のルートを取り出す。
            # list のインデックスアクセスは O(1)。カーソルを1つ前に進める。
            val: int = postorder[post_idx[0]]
            post_idx[0] -= 1

            # ルートノードを作成する。
            node = TreeNode(val)

            # dict から O(1) でルートの inorder 上の位置を取得する。
            # この位置より「左側」が左部分木、「右側」が右部分木になる。
            mid: int = idx_map[val]

            # ★重要★ 右部分木を先に再帰する理由：
            # postorder を末尾から逆順に消費すると「ルート→右→左」の順になる。
            # つまり次の pop は「右部分木のルート」を指している。
            # 左を先にすると消費順序がずれて誤った木になってしまう。
            node.right = dfs(mid + 1, right)  # 右：mid+1 〜 right
            node.left  = dfs(left, mid - 1)   # 左：left 〜 mid-1

            return node

        # inorder の全範囲（0 〜 n-1）を対象に木を構築して返す
        return dfs(0, len(inorder) - 1)

事前準備:
  idx_map   = { 9:0, 3:1, 15:2, 20:3, 7:4 }
  post_idx  = [4]  ← postorder の末尾インデックス

dfs(0, 4)  ← inorder 全体の範囲
  val = postorder[4] = 3    post_idx: [4]→[3]
  mid = idx_map[3] = 1
  node = TreeNode(3)
  ├─ node.right = dfs(2, 4)
  │    val = postorder[3] = 20   post_idx: [3]→[2]
  │    mid = idx_map[20] = 3
  │    node = TreeNode(20)
  │    ├─ node.right = dfs(4, 4)
  │    │    val = postorder[2] = 7    post_idx: [2]→[1]
  │    │    node = TreeNode(7) ← 葉ノード（左右None）
  │    │    return TreeNode(7) ✅
  │    └─ node.left = dfs(2, 2)
  │         val = postorder[1] = 15   post_idx: [1]→[0]
  │         node = TreeNode(15) ← 葉ノード
  │         return TreeNode(15) ✅
  │    return TreeNode(20) ✅
  └─ node.left = dfs(0, 0)
       val = postorder[0] = 9    post_idx: [0]→[-1]
       node = TreeNode(9) ← 葉ノード
       return TreeNode(9) ✅

最終結果:
      3
     / \
    9   20
       /  \
      15    7   ✅

処理フローチャート

計算量分析

📖 用語集

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