算法题 19 二叉平衡树检查 牛客网 CC150
实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。
给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。
解题代码：时间复杂度为O(NlogN) N为树中的节点数
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Balance: def isBalance(self, root): # write code here if not root: return True heightDiff=self.getHeight(root.left)-self.getHeight(root.right) if abs(heightDiff)>1: return False else: return self.isBalance(root.left) and self.isBalance(root.right) def getHeight(self,root): if not root: return 0 return max(self.getHeight(root.left),self.getHeight(root.right))+1
解题代码二：优化版，时间复杂度为O(N),空间复杂度为O(H)，H为树的高度
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Balance: def isBalance(self, root): # write code here if self.checkHeight(root)==-1: return False else: return True def checkHeight(self,root): if not root: return 0 #高度为0 leftHeight=self.checkHeight(root.left) if leftHeight==-1: return -1 # 不平衡 rightHeight=self.checkHeight(root.right) if rightHeight==-1: return -1 # 不平衡 heightDiff=leftHeight-rightHeight if abs(heightDiff)>1: return -1 else: return max(leftHeight,rightHeight)+1
原文：https://www.cnblogs.com/yanmk/p/9343177.html