题解 | #判断是不是平衡二叉树#
判断是不是平衡二叉树
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
Python3递归。所谓自底向上，就是利用非平衡的传染性：有非平衡子树，自己一定非平衡。所以只要子树出现非平衡，就返回-1（非正常深度，正常的深度>=0），子树都平衡，才计算高度差并返回
class Solution: # 自底向上，非平衡直接返回-1（-1有传染性，即非平衡往上直接判断非平衡）。平衡再计算深度返回 def IsBalanced_Solution(self, pRoot): def recur(pRoot): if pRoot is None: #空树没有深度 return 0 left = recur(pRoot.left) #计算左子树深度 if left == -1: return -1 right = recur(pRoot.right) #计算右子树深度 if right == -1: return -1 return max(left, right) + 1 if abs(left - right) <= 1 else -1 return recur(pRoot) != -1 #-1表示深度差大于等于2
