用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

Arnab Chakraborty

更新于：2020年8月27日

94次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习