LeetCode 102. Binary Tree Level Order Traversal
入力値として二分木が与えられ、階層ごとのノード値を左から順番に列挙したリストの配列を返せ、というもの。
このような入力の場合、[[3],[9,20],[15,7][6,1,2]]を返す。
この問題は、BFS（幅優先探索）を使ってノードを探索すると効率が良いようだ。wikipedia
今回の場合は、ルートのノードから順に階層を下に降りつつすべてのノードを走査する。
走査したノードを追加するためのキューと、今いる階層の値のリストに適宜値を追加していく。
具体的な処理の流れを図で説明する。
説明のための要素として、処理対象のノードを追加するための「キュー」、同階層のノード値をバッファしておくための「同階層の値リスト」、最終的に返すリストの「結果リスト」の3つを考える。
ルートノードから処理を開始する。
ルートノードをキューに入れ、キューから取り出す。
取出した3ノードの値を値リストに追加する。
その後、3ノードの子ノードである、9ノード、20ノードをキューに追加する。
ルートノードの階層はすべて走査が完了したため、値リストを結果リストに追加する。
キューの先頭の9ノードを取り出す。
取り出した9ノードの値を値リストに追加する。
9ノードには子ノードがないため、キューには何も登録しない。
ルートノードの階層はすべて走査が完了したため、値リストを結果リストに追加する。
キューの先頭の20ノードを取り出す。
取り出した20ノードの値を値リストに追加する。
20ノードの子ノードである、15、7ノードをキューに追加する。
第2階層のノードはすべて走査が完了したため、値リストを結果リストに追加する。
キューの先頭の15ノードを取り出す。
取り出した15ノードの値を値リストに追加する。
15ノードの子ノードである6、1ノードをキューに追加する。
キューの先頭の7ノードを取り出す。
取り出した7ノードの値を値リストに追加する。
7ノードの子ノードである2ノードをキューに追加する。
第3階層の走査が完了したため、値リストを結果リストに追加する。
キューの先頭の6ノードを取り出す。
取り出した6ノードの値を値リストに追加する。
6ノードには子ノードがないため、キューには何も登録しない。
同様に1ノードについても処理を行う。
同様に2ノードについても処理を行う。
第4階層のノードの操作が完了したため、値リストを結果リストに追加する。
キューの中身が空になったため、処理を完了し、出来上がった結果リストを返す。
class Solution {
function levelOrder($root) {
$result = [];
$queue = [];
$queue[] = $root;
while (count($queue)) {
$queue_len = count($queue);
$level = [];
for ($i=0; $i<$queue_len; $i++) {
$node = array_splice($queue, 0, 1, [])[0];
if ($node) {
$level[] = $node->val;
$queue[] = $node->left;
$queue[] = $node->right;
}
}
if ($level) {
$result[] = $level;
}
}
return $result;
}
}
Discussion