Python 中的平衡二叉树
pythonserver side programmingprogramming更新于 2024/2/18 17:14:00
在二叉树中，每个节点包含两个子节点，即左子节点和右子节点。假设我们有一棵二叉树，我们需要检查这棵树是否平衡。如果左子树和右子树的高度差小于或等于"1"，则称二叉树是平衡的。
示例
输入 1:
输出:
True
说明:
给定的二叉树为 [1,2,3, NULL, NULL, 6, 7]。其左子树与右子树的高度差为"1"，因此是一棵高度平衡的树。
输入-2:
输出:
False
解释:
给定的二叉树为 [1,2,3,4, NULL, NULL,NULL,5]。它的左子树和右子树的高度差大于"1"，因此它不是高度平衡树。
解决此问题的方法
解决此问题的递归方法是找到左子树和右子树的高度，然后检查 (height(leftsubtree) - height(rightsubtree) <= 1) 是否成立，并相应地返回 True 或 False。然后，我们将递归检查二叉树的每个节点。
- 输入二叉树的节点。
- 定义一个函数来查找树的高度。
- 一个布尔函数，用于递归检查左子树和右子树的高度差是否不超过"1"，然后返回 True。
- 返回结果。
示例
class treenode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# 函数用于查找左子树和右子树的高度
class height:
def __init__(self):
self.height = 0
# 函数用于检查树是否平衡
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")
运行上述代码将生成如下输出:
输出
平衡
给定二叉树 [1, 2, 3, NULL, NULL, 6, 7]。其左子树和右子树的高度差等于"1"，因此它是一棵高度平衡的树。
