什么是平衡二叉树?如何判断一个二叉树是否为平衡二叉树?
时间: 2023-12-20 20:31:26 浏览: 119
平衡二叉树是一种特殊的二叉搜索树,它的左右子树的高度差不超过1,以此来保证树的高度不会过高,从而保证了树的各种操作的时间复杂度都是O(logn)级别的。判断一个二叉树是否为平衡二叉树,需要对每个结点的左右子树高度进行比较,如果左右子树高度差超过1,则该二叉树不是平衡二叉树。可以通过递归遍历二叉树的每个结点,计算左右子树的高度差来判断是否为平衡二叉树。
以下是判断一个二叉树是否为平衡二叉树的Python代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
left_height = self.get_height(root.left)
right_height = self.get_height(root.right)
if abs(left_height - right_height) > 1:
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
def get_height(self, node: TreeNode) -> int:
if not node:
return 0
return max(self.get_height(node.left), self.get_height(node.right)) + 1
```
阅读全文