首页判断一个二叉树是否为平衡二叉树

判断一个二叉树是否为平衡二叉树

时间: 2025-01-27 22:14:06 浏览: 54

判断一个二叉树是否为平衡二叉树可以通过以下步骤实现： 1. **定义平衡二叉树的性质**：平衡二叉树是一种二叉树，其中每个节点的左子树和右子树的高度差不超过1。 2. **递归检查每个节点**：对于每个节点，检查其左子树和右子树的高度差是否不超过1。如果所有节点都满足这个条件，则该二叉树是平衡二叉树。 3. **计算子树高度**：在检查每个节点时，需要计算其左子树和右子树的高度。可以使用递归方法计算子树的高度。以下是一个示例代码，展示了如何判断一个二叉树是否为平衡二叉树： ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def is_balanced(root): def check(node): if node is None: return 0 left = check(node.left) if left == -1: return -1 right = check(node.right) if right == -1 return max(left, right) + 1 return check(root) != -1 # 示例用法 # 构建一个平衡二叉树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.left = TreeNode(6) root.right.right = TreeNode(7) print(is_balanced(root)) # 输出: True # 构建一个不平衡的二叉树 unbalanced_root = TreeNode(1) unbalanced_root.left = TreeNode(2) unbalanced_root.left.left = TreeNode(3) print(is_balanced(unbalanced_root)) # 输出: False ``` 在这个示例中，`is_balanced` 函数通过递归检查每个节点的高度差来判断二叉树是否为平衡二叉树。

阅读全文