用Python檢查給定的二叉樹是否像紅黑樹一樣高度平衡

假設存在一棵紅黑樹，這裡節點的最大高度最多是最小高度的兩倍。如果我們有一個二叉搜尋樹，我們必須檢查以下屬性。對於每個節點，從葉子到節點的最長路徑長度不大於從節點到葉子的最短路徑上的節點數量的兩倍。

所以，如果輸入是這樣的

那麼輸出將為True，因為它已平衡。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式solve()。這將接受根節點、最大高度和最小高度。
  • 如果根節點為空，則
    • 最大高度 := 0，最小高度 := 0
    • 返回True
  • 左最大 := 0，左最小 := 0
  • 右最大 := 0，右最小 := 0
  • 如果solve(root.left, left_max, left_min) 為False，則
    • 返回False
  • 如果solve(root.right, right_max, right_min) 為False，則
    • 返回False
  • 最大高度 := 左最大和右最大中的最大值 + 1
  • 最小高度 := 左最小和右最小中的最小值 + 1
  • 如果最大高度 <= 2 * 最小高度，則
    • 返回True
  • 返回False
  • 從主方法執行以下操作：
  • 最大高度 := 0，最小高度 := 0
  • 返回solve(root, max_height, min_height)

示例

讓我們看看下面的實現以更好地理解：

 線上演示

class TreeNode:
   def __init__(self, key):
      self.data = key
      self.left = None
      self.right = None
def solve(root, max_height, min_height) :
   if (root == None) :
      max_height = min_height = 0
      return True
   left_max=0
   left_min=0
   right_max, right_min=0,0
   if (solve(root.left, left_max, left_min) == False) :
      return False
   if (solve(root.right, right_max, right_min) == False) :
      return False
   max_height = max(left_max, right_max) + 1
   min_height = min(left_min, right_min) + 1
   if (max_height <= 2 * min_height) :
      return True
   return False
def is_tree_balanced(root) :
   max_height, min_height = 0,0
   return solve(root, max_height, min_height)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(100)
root.right.left = TreeNode(50)
root.right.right = TreeNode(150)
root.right.left.left = TreeNode(40)
print(is_tree_balanced(root))

輸入

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(100)
root.right.left = TreeNode(50)
root.right.right = TreeNode(150)
root.right.left.left = TreeNode(40)

輸出

True

更新於：2020年8月27日

94次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始學習
廣告