Leetcode 102二分木レベル順序横断

Leetcode 102の解法二分木レベル順序横断Click here そして、あなたの自己を試してみてください!

leetcode問題文

2進木の根を与えられて、そのノードの値のレベルオーダー横断を返します.(すなわち、左から右、レベルごとに).
例:
例1画像:

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3: 
Input: root = []
Output: []

初期思考

幅の最初の検索!

破壊する

BFSを使用してツリーを横断し、現在のレベルの配列で指定したレベルのすべてのノードを収集できます.それぞれのcurrentLevel配列を結果配列に格納できます.一旦我々が我々の解決を終えるならば、我々の解決は結果に含まれなければなりません.
あなたがBFSを実装する方法に慣れていないならば、ここで読み続けてください.この問題に関連するBFS実装を説明します.あなたがよく知られているならば、スキップして自由に感じてください.

BFSの実装

ループとループのためにBFSを実装するためにキューを使うことができます.通常、キューとwhileループが必要ですが、forループは問題によってオプションです.また、これはただ一つの方法です.
キーをオフにするには、ルートノードでキューを初期化します.それが空でない間、我々は待ち行列を通して繰り返され続けます.

我々のwhileループで反復すると、キューの現在の長さをキャプチャします.この長さは、現在のレベルのノード数を表します.私たちの例を見て、最初の反復のために、currentLengthは1に等しくなります.次の2つに等しくなり、最後の反復は再び2になります.これは、我々が問題を解決し続けるとき、より明らかになるでしょう.

currentLengthの格納はここで重要です.それはレベルレベルのレベルでノード上で動作できるように、それぞれのレベルの境界を知ることができる情報です.

Important Note. Make sure to save currentLevel as a variable, and don’t use queue.length. As you will see we are always adding child nodes to the queue so the length will change.

forループの中でグラブするノードは全てcurrentlevelに属します.この問題については、各レベルを収集し、配列で返します.したがって、我々のキューからshift ()を行うたびに、値を現在のレベルにプッシュすることができます.
次のレベルを収集するには、現在のノードが子を持つかどうかを確認します.そうした場合は、キューにプッシュします.
繰り返しが終了すると、我々のキューは、次のレベルを持っている必要があります我々の結果は、最初のレベルを持つ必要があります.

これらの手順に従って、我々はすべてのレベルを収集します!いいね.

アルゴリズム計画

アプローチ概要

rootがない場合は

ルートノードでキューを初期化する

結果配列を初期化する

キューが空でない間

現在の配列を初期化する

キューの現在の長さをキャプチャする

forループを宣言し、キューを通して0からcurrentLengthまで繰り返します

キューからのshift ()

を返します.左、プッシュノード.左へ

を返します.右、プッシュノード.待ち行列

プッシュノード.現在のレベルまでのval

結果をcurrentLevelにプッシュする

結果を返す

コード

const levelOrder = (root) => {

    if (!root) return []

    const results = [];
    const queue = [root];

    while (queue.length > 0) {
        const currentLength = queue.length;
        const currentLevel = [];

        for(let i = 0; i < currentLength; i++) {
            const node = queue.shift();
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
            currentLevel.push(node.val);
        }

        results.push(currentLevel);
    }

    return results;
}

概要

ツリー内のすべてのノードを訪問しているので,このアルゴリズムの時間計算量はo(n)である.空間の複雑さはo(n)＋o(k)であり,kは最も節点のあるレベルである.これは私たちのキューができる最大のサイズを表します.
もう一つの面白い部分は、我々が使っているキューです.私の解決法では、私はちょうど普通のJS配列を使用しています.これは操作に関してキューのように動作しますが、真のキュー実装から得られる性能を与えません.この部分を分析することはこのブログのポストの範囲を超えていますが、それを呼ぶことは重要です.
ホープは、この役立つ発見!