检查平衡性
题目描述 算法思想
对于平衡树的概念，题目已经叙述清楚。 那么对于解决该题，其实方法显而易见，也就是递归对树进行遍历，统计每个节点的左右子树是否满足平衡，递归返回时，如果一个节点的左右子树均满足平衡，则返回Ture，否则返回False。
代码实现
方法一
这里利用了一个传递错误的标记，每当遇到一个节点不满足时，向上传递该标记。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isBalanced(self, root: TreeNode) -> bool: def check_height(root): if not root: return -1 leftheight = check_height(root.left) if leftheight == float('inf') : return float('inf') rightheight = check_height(root.right) if rightheight == float('inf') : return float('inf') totalheight = abs(leftheight - rightheight) if totalheight > 1: return float('inf') else: return max(leftheight, rightheight) + 1 return check_height(root) != float('inf')方法二
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isBalanced(self, root: TreeNode) -> bool: def check_height(root): if not root: return 0 return max(check_height(root.right), check_height(root.left)) + 1 if not root: return True if abs(check_height(root.right) - check_height(root.left)) > 1: return False return self.isBalanced(root.right) and self.isBalanced(root.left)参考题解
作者：user227 链接：https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/solution/zhong-xu-bian-li-di-gui-andfei-di-gui-by-user227/ 来源：力扣（LeetCode）
