問題
あるpreorder と inorder を
preorderは前順 (自分、 左の 部分木、 右の 部分木の 順) に たどった並びです inorderは中順 (左の 部分木、 自分、 右の 部分木の 順) に たどった並びです - 木の
値は どれも 違います。 2 つの 並びは 同じ 木から 作られた 正しい並びです - 新しい
節は、 Python では TreeNode(値)、JavaScript では new TreeNode(値)、Go では &TreeNode{}で作れます。 どれも val(値)、left(左の子)、 right(右の子) を 持ち、 子は 最初は 空です。 Go では Val、Left、Rightと大文字で 始まります - 節の
数は 1 以上 500 以下、 値は どれも -1000 以上 1000 以下です - 節の
数を n として、 時間が O(n) で 済む 書き方を 目指してください
出力のnull で、null は
入力と出力の例
例 1
前順の
入力
preorder = [4, 2, 1, 3, 7, 6]
inorder = [1, 2, 3, 4, 6, 7]出力
[4, 2, 7, 1, 3, 6]例 2
根の -1 は
入力
preorder = [-1, 5, 8]
inorder = [-1, 8, 5]出力
[-1, null, 5, 8]例 3
中順が
入力
preorder = [9, 6, 2]
inorder = [2, 6, 9]出力
[9, 6, null, 2]面接での聞かれ方
面接では、
- 「前順と
中順の 並びから、 元の 二分木を 作ってください」 - 最初の
書き方を 出すと 「中順の 中で 根を 探す所は、 全体で 何回の 比べに なりますか？」と 計算量を 詰められます - 書き終えた
あとに 「後順と 中順なら、 どこを 変えますか？」 「前順と 後順だけでは、 なぜ 1 つに 決まらないのですか？」と 広げて 聞かれます - 「同じ
値が 入っていたら？」 「節が もっと 多く、 再帰が 深くなりすぎるなら？」と、 前提を 崩して 聞かれる こともあります
値が
アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。
まず
段 1
まず、
段 2
左右の
段 3
2 つの
段 4
前順の
解答
Python
Python
def tree_from_orders(
preorder, inorder
):
at = {}
n = len(inorder)
for i in range(n):
at[inorder[i]] = i
vals = iter(preorder)
return grow(
vals, at, 0, n - 1
)
def grow(vals, at, lo, hi):
if lo > hi:
return None
v = next(vals)
node = TreeNode(v)
mid = at[v]
node.left = grow(
vals, at, lo, mid - 1
)
node.right = grow(
vals, at, mid + 1, hi
)
return nodeJavaScript
JavaScript
function treeFromOrders(
preorder, inorder
) {
const at = new Map();
inorder.forEach((v, i) => {
at.set(v, i);
});
let next = 0;
function grow(lo, hi) {
if (lo > hi) {
return null;
}
const v = preorder[next];
next++;
const nd = new TreeNode(v);
const mid = at.get(v);
nd.left = grow(
lo, mid - 1
);
nd.right = grow(
mid + 1, hi
);
return nd;
}
return grow(
0, inorder.length - 1
);
}Go
Go
func treeFromOrders(
preorder, inorder []int,
) *TreeNode {
at := map[int]int{}
for i, v := range inorder {
at[v] = i
}
next := 0
return grow(
preorder, at, &next,
0, len(inorder)-1,
)
}
func grow(
pre []int, at map[int]int,
next *int, lo, hi int,
) *TreeNode {
if lo > hi {
return nil
}
v := pre[*next]
*next++
node := &TreeNode{Val: v}
mid := at[v]
node.Left = grow(
pre, at, next, lo, mid-1,
)
node.Right = grow(
pre, at, next, mid+1, hi,
)
return node
}lo と hi は、iter でnext で 1 つずつ
計算量
- 時間は O(n) です。
辞書を 作るのに O(n)、 その あとは 節を 1 つ作る ごとに 辞書を 1 回引くだけです - 使う
記憶は、 返す木の n 個の 節の ほかに O(n) です。 辞書が n 個の 値を 持ちます。 再帰の 深さは 木の 高さの 分で、 1 本道の 木では n に なります。 節が 500 以下なので、 Python の 再帰の 上限 (1000 段) には 届きません
よく
- 根の
位置を 毎回 中順の 先頭から探す。 inorder.index(v)やindexOfを毎回呼ぶと、 1 本道の 木で O(n²) に なります。 値から 位置を 引く 辞書を 最初に 1 回だけ作ります - 並びを
切り出して渡す。 部分木ごとに 前順と 中順の 写しを 作ると、 時間も 記憶も O(n²) まで 増えます。 範囲の 両端の 番号だけを渡します - 右の
部分木を 先に作る。 前順は 「自分、左、右」の 順なので、 指を 共有する 書き方では 左を 作り終えてから 右を 作ります。 順を 入れ替えると、 右の 部分木が 左の 値を 取ってしまい、 木が壊れます - 同じ値が
ある ときにも、 この 書き方を そのまま使う。 辞書は 1 つの 値に 1 つの 位置しか 持てません。 同じ 値が 入る 木では、 中順の どこが 根かが 決まらず、 2 つの 並びから 木が 1 つに 決まらない こともあります - 深い木で
再帰の 上限に当たる。 節が もっと 多く 1 本道に 近い木なら、 Python は 再帰の 上限で 止まります。 その 大きさを 聞かれたら、 スタックで 節を 積みながら 前順を 読み進める 繰り返しの 書き方に すると答えます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「前順の
先頭が 根で、 中順では その 左が 左の 部分木、 右が 右の 部分木です。 素直に 書くと、 中順の 中で 根を 探すのと 並びの 切り出しで O(n²) に なります。 そこで、 値から 中順の 位置を 引く 辞書を 最初に 作り、 範囲は 両端の 番号で 渡します。 前順は 1 本の 指で 先頭から 読み、 左を 作り終えてから 右を 作ります。 値が どれも 違うことが 前提です。 時間は O(n)、 記憶は 辞書の 分の O(n) です。」
書き終えたら、
「例 1 で
たどります。 指は 前順の 4 を 指していて、 中順で 4 は 番号 3 です。 左は 番号 0 から 2 で、 指が 進んで 2 を 取り、 中順の 番号 1 で 左右に 分かれて 1 と 3 が 付きます。 左を 作り 終えると 指は 7 を 指しています。 右は 番号 4 と 5 で、 7 は 番号 5 なので 左に 6 が 付き、 右は 空です。」