🔖

LeetCode 102. Binary Tree Level Order Traversal

2022/08/05に公開約2,700字

https://leetcode.com/problems/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ノードの子ノードである、157ノードをキューに追加する。
第2階層のノードはすべて走査が完了したため、値リストを結果リストに追加する。

キューの先頭の15ノードを取り出す。
取り出した15ノードの値を値リストに追加する。
15ノードの子ノードである61ノードをキューに追加する。

キューの先頭の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

ログインするとコメントできます