Pythonの平衡二分木

二分木では、各ノードに2つの子、つまり左の子と右の子が含まれます。二分木があり、その木がバランスしているかどうかを確認する必要があるとしましょう。左のサブツリーと右のサブツリーの高さの差が「1」以下の場合、二分木はバランスが取れていると言われます。

例

入力-1：

出力：

True

説明：

与えられた二分木は[1,2,3、NULL、NULL、6、7]です。左側のサブツリーと右側のサブツリーの高さの差は「1」に等しいため、高さのバランスが取れたツリーになります。

入力-2：

出力：

False

説明：

与えられた二分木は[1,2,3,4、NULL、NULL、NULL、5]です。左側のサブツリーと右側のサブツリーの高さの差が「1」より大きいため、高さのバランスが取れたツリーではありません。

この問題を解決するためのアプローチ

この問題を解決するための再帰的なアプローチは、左側のサブツリーと右側のサブツリーの高さを見つけて、（height（leftsubstree）--height（rightsubtree）<=1）かどうかを確認し、それに応じてTrueまたはFalseを返すことです。次に、バイナリツリーの各ノードを再帰的にチェックします。

• 二分木のノードを入力します。
• 木の高さを見つける関数を定義します。
• 左のサブツリーと右のサブツリーの高さの差が「1」以下であるかどうかを再帰的にチェックし、Trueを返すブール関数。
• 結果を返します。

例

class treenode:
   def __init__(self, data):
      self.data = data
      self.left = self.right = None
# funtion to find the height of the left subtree and right subtree
class height:
   def __init__(self):
      self.height = 0
# function to check if the tree is balanced or not
def isBalanced(root):
   lh = height()
   rh = height()
   if root is None:
      return True
   return (
      (abs(lh.height - rh.height) <= 1)
      and isBalanced(root.left)
      and isBalanced(root.right)
   )
root = treenode(1)
root.left = treenode(2)
root.right = treenode(3)
root.left.left = None
root.left.right = None
root.right.left = treenode(6)
root.right.right = treenode(7)
if isBalanced(root):
   print("Balanced")
else:
   print("Not Balanced")

上記のコードを実行すると、次のように出力が生成されます

出力

Balanced

与えられた二分木[1、2、3、NULL、NULL、6、7]。左側のサブツリーと右側のサブツリーの高さの差は「1」に等しいため、高さのバランスが取れたツリーになります。