2026-10-26
level_order.rs
fn level_order(sorted: &[u32]) -> Vec<u32> {
}
昇順に並んだ重複のないキーの列 sorted を、空の二分探索木へどの順に挿入するかを返す level_order を書いてください。木は、列の中央のキー(長さが偶数なら中央の2つのうち左)を根にし、その左側と右側の列にも同じ規則を当てて子を決めたものです。返すのは、この木のキーを根から1段ずつ、各段の中では左から順に並べた列です。空の列には空の Vec を返します。
入力例 1
level_order(&[1, 2, 3, 4, 5, 6, 7])
出力例 1
[4, 2, 6, 1, 3, 5, 7]
入力例 2
level_order(&[10, 20, 30, 40])
出力例 2
[20, 10, 30, 40]
入力例 3
level_order(&[])
出力例 3
[]
Reference
use std::collections::VecDeque;
fn level_order(sorted: &[u32]) -> Vec<u32> {
let mut out = Vec::with_capacity(sorted.len());
let mut queue = VecDeque::from([sorted]);
while let Some(s) = queue.pop_front() {
if s.is_empty() {
continue;
}
let mid = (s.len() - 1) / 2;
out.push(s[mid]);
queue.push_back(&s[..mid]);
queue.push_back(&s[mid + 1..]);
}
out
}
まだキーを並べていない部分木を、昇順の部分列として VecDeque に入れておき、先頭から1つずつ取り出します。取り出した部分列の中央がその部分木の根なので、それを out に足し、左右の部分列を末尾に入れます。ある段の部分木をすべて取り出してから次の段の部分木に進むので、out は根に近い段から、各段の中では左から順に並びます。
部分列は &s[..mid] のように元のスライスを借りるだけで、キーを写すのは out に入れるときの1回だけです。空の部分列は子がないことを表すので、取り出したら飛ばします。長さ 0 の列をここで除いているので、(s.len() - 1) / 2 が桁あふれすることはありません。長さが偶数なら、この式は中央の2つのうち左を選びます。
この順に挿入すると、どのキーも親より後に、親の左右どちらかの部分列から来るので、木は規則で決めた形のとおりに育ちます。キーが n 個なら高さは n の2進数の桁数(7個なら 3)で、昇順のまま挿入したときの高さ n より大きく下がります。
掲載したのは参考実装で、唯一の正解ではありません。部分列の代わりに添字の範囲 (lo, hi) をキューに入れても、同じ順が得られます。