毎日のアルゴリズム: 二分木のレベルトラバーサル

[[423982]]

バイナリ ツリーが与えられた場合、そのノード値のボトムアップ レベルのトラバーサルを返します。 （つまり、リーフノードが配置されているレイヤーからルートノードが配置されているレイヤーまで、左から右にトラバースします）

例えば、二分木[3,9,20,null,null,15,7]が与えられた場合、

3

/ \

9 20

/ \

15 7

ボトムアップ レベルのトラバーサルを次のように返します。

 [
  [15,7]、
  [9,20]、
  [3]
 ]

解決策 1: BFS (幅優先探索)

BFS は、各レイヤーのノードをレイヤーごとに走査します。この質問では各レイヤーのノード値を返す必要があるため、BFS はこの問題に非常に適しています。 BFS は補助構造としてキューを使用する必要があります。まずルート ノードをキューに入れてから、キューのトラバースを続けます。

 const levelOrderBottom =関数(ルート) {
    if(!root) return []
    res = []とします。
        キュー = [ルート]
    while(キューの長さ) {
        curr = []とします。
温度= []
        while(キューの長さ) {
            ノードをキュー.shift() にします。
            curr.push(ノード.val)
            if( node.left ) temp.push ( node.left )
            if( node.right ) temp.push ( node.right )
        }
        res.push(カレント)
        キュー =一時 
    }
 res.reverse()を返す
};

複雑性分析

• 時間計算量: O(n)
• 空間計算量: O(n)

ソリューション 2: DFS (深さ優先探索)

DFS は、ツリーのノードをその深さに沿ってトラバースし、ツリーのブランチを可能な限り深く検索します。

この問題における DFS の主な問題は、DFS がレベルを横断しないことです。再帰プロセス中に同じレベルのノードを同じリストに配置するには、再帰中に各ノードの深さを記録する必要があります。新しいノードに再帰する場合は、深さに対応するリストの最後にノードを配置します。

新しい深度 depth にトラバースするときに、depth に対応するリストが最終結果 res に作成されていない場合は、深度のすべてのノードを保存するために res に新しいリストを作成する必要があります。

 const levelOrderBottom =関数(ルート) {
    定数res = []
    var dep =関数(ノード、深さ){
        if(!ノード)戻り値 
        res[深さ] = res[深さ]||[]
        res[深さ].push(node.val)
        dep(ノード.left , 深さ+1)
        dep(ノード.right 、深さ + 1)
    }
    dep(ルート, 0)
 res.reverse()を返す
};

複雑性分析:

• 時間計算量: O(n)
• 空間計算量: O(h)、ここでhは木の高さ