毎日のアルゴリズム: バランスのとれた二分木

[[426529]]

この記事はWeChatの公開アカウント「3分でフロントエンドを学ぶ」から転載したもので、著者はsisterAnです。この記事を転載する場合は、「3分で学ぶフロントエンド」公式アカウントまでご連絡ください。

木の基礎については、こちらをご覧ください: 初心者のための木

二分木が与えられた場合、それが高さバランスの取れた二分木であるかどうかを判断します。

この問題では、高度にバランスのとれた二分木は次のように定義されます。

バイナリツリー内の各ノードの左側のサブツリーと右側のサブツリー間の高さの差の絶対値は 1 を超えません。

例1:

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

true を返します。

例2:

二分木[1,2,2,3,3,null,null,4,4]が与えられた場合

false を返します。

解決策 1: トップダウン (ブルートフォース)

解決方法: 各ノードの左サブツリーと右サブツリーの最大高さの差を上から下まで比較します。バイナリツリー内の各ノードの左サブツリーと右サブツリーの最大高さの差が 1 以下、つまり各サブツリーのバランスが取れている場合、バイナリツリーはバランスの取れたバイナリツリーです。

コード実装:

 const isBalanced =関数(ルート) {
  if(!root)戻り値 真実 
 Math.abs (depth(root.left ) -depth( root.right ) ) <= 1を返す
        && isBalanced(ルート.left )
        && isBalanced(ルート.right )
 }
 const depth =関数(ノード) {
    if(!node) は-1を返します
1 + Math.max ( depth(node.left ) ,depth(node.right ) )を返します。
 }

複雑性分析:

時間計算量: O(nlogn)、深さを計算する際に多くの冗長な操作がある
空間計算量: O(n)

解決策2: ボトムアップ（最適化）

解決方法: バイナリツリー (左ルートと右ルート) の後続のトラバーサルを使用して、下から上へのサブツリーの最大の高さを返し、各サブツリーがバランスの取れたツリーであるかどうかを判断します。バランスが取れている場合は、その高さを使用して親ノードがバランスが取れているかどうかを判断し、親ノードの高さを計算します。バランスが取れていない場合は、-1 を返します。

バイナリツリー内の各ノードの左サブツリーと右サブツリーの深さを走査して比較します。

左と右のサブツリーの深さを比較します。差が 1 より大きい場合は、現在のサブツリーが不均衡であることを示すフラグ -1 を返します。
左と右のサブツリーのいずれかがバランスが取れていない場合、または左と右のサブツリーの差が 1 より大きい場合、バイナリツリーは不均衡です。
左と右のサブツリーのバランスが取れている場合は、現在のツリーの深さ（左と右のサブツリーの最大深さ + 1）を返します。

コード実装:

 const isBalanced =関数(ルート) {
 balanced(root) !== -1を返す
};
 const balanced =関数(ノード) {
    if (!node) が0 を返す
    定数left = balanced ( node.left )
    定数right = balanced( node.right )
    if (左=== -1 ||右=== -1 || Math.abs (左-右) > 1) {
 -1を返す
    }
 Math.max ( left , right )+1を返す
}