二分木（応用）二分木の再構築, 二分木のシリアライズ

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Construct Binary Tree from Preorder and Inorder Traversal	★★★	高	二分木の再構築
Construct Binary Tree from Inorder and Postorder Traversal	★★★	高	二分木の再構築
Serialize and Deserialize Binary Tree	★★★★	中	Serialize and Reconstruct Binary Tree (シリアライズと再構築)
Unique Binary Search Trees II	★★★★	中	Serialize and Reconstruct Binary Tree (シリアライズと再構築)
All Possible Full Binary Trees	★★★★	中	Serialize and Reconstruct Binary Tree (シリアライズと再構築)

巡回から二分木の再構築

ここでいう木の再構築とは、2種類の巡回の出力から二分木を復元することを指します。ただし 前提として木の値がユニークである 必要があります。なぜなら同じ値が巡回の出力に存在する場合、どのノードであるかが特定できないためです。例えば以下の2つの二分木は別の構造をとりますが、全ての巡回で出力が同じ[1, 1]となります。

preorder  = [1, 1]
inorder   = [1, 1]
postorder = [1, 1]