[数据结构与算法]110平衡二叉数

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

题解：

1. 要判断每个分支的高度，一旦有一个分支不是高度平衡二叉树，就返回Flase，只有左右子树都是高度平衡二叉树，才为True

2. 用递归左右 每个分支的高度，求每个分支的高度又是一个递归

求一棵树的高度：

def maxhigth(r):
        if r==None:
            return 0
        leftmax =  maxhigth(r.left)+1
        rightmax = maxhigth(r.right)+1
        return max(rightmax,leftmax))

判断是否为高度平衡二叉树，用先序来递归每个分支的高度

class Solution:
    def maxhigth(self,r):
        if r==None:
            return 0
        leftmax =  self.maxhigth(r.left)+1
        rightmax = self.maxhigth(r.right)+1
        return max(rightmax,leftmax)#,min(rightmin,leftmin)
    
    def isBalanced(self, root: TreeNode) -> bool:
        if root==None:
            return True
        left=self.maxhigth(root.left)
        right = self.maxhigth(root.right)
        lnode = root.left
        rnode = root.right
        if abs(left-right)>1:
            return False
        lresult = self.isBalanced(lnode)
        rresult = self.isBalanced(rnode)
        if lresult ==False or rresult==False:
            return False
        else: return True