检查给定的二叉树是否像 Python 中的红黑树一样高度平衡

pythonserver side programmingprogramming更新于 2025/10/17 5:00:17

假设有一棵红黑树，这里节点的最大高度最多是最小高度的两倍。如果我们有一棵二叉搜索树，我们必须检查以下属性。对于每个节点，最长的叶子到节点路径的长度不超过从节点到叶子的最短路径上节点的两倍。

因此，如果输入如下

那么输出将为 True，因为这是平衡的。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数solve()。这将取 root、max_height、min_height
如果 root 为空，则
- max_height := 0, min_height := 0
- 返回 True
left_max := 0, left_min := 0
right_max := 0, right_min := 0
如果solve(root.left, left_max, left_min)与False相同，则
- 返回 False
如果solve(root.right, right_max, right_min)与False相同，则
- 返回 False
max_height := left_max 和的最大值right_max + 1
min_height := left_min 和 right_min 的最小值 + 1
如果 max_height <= 2 * min_height，则
- 返回 True
返回 False
从主方法执行以下操作 −
max_height := 0, min_height := 0
返回 resolve(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)