平衡树：二叉树的每个节点的左子树和右子树的高度差不超过1.

• 如果一个二叉树是空的，那么其高度为0；
• 如果一个二叉树的只有一个节点，那么其高度为1；
• 对于非叶子节点的二叉树，其高度为左子树与右子树高度的最大值
  二叉树的高度可以用递归算法来实现：
• 如果输入的是空节点，高度为0；
• 如果输入的是叶子节点，左右子树都为空，则其高度为1；
• 如果输入的是非叶子节点，那么分别计算左右子树的高度，选取最大值加1，即为二叉树的高度。
  树的节点实现
  定义二叉树节点的数据结构，其包含value以及左孩子与右孩子

class TreeNode:
    def __init__(self, v):
        self.value = v
        self.left = self.right = None

排序树的实现：
构建排序二叉树，创建TreeUtil类，当加入节点的值比当前节点小，则进入左子树，当加入节点值比当前节点大，则进入右子数。
向排序树中添加叶子节点函数为 addTreeNode(self, node)

class TreeUtil:
    def __init__(self):
        self.root = None
    def addTreeNode(self, node):
        if self.root = None:
            self.root = node
        currentNode = self.root
        prevNode = self.root
        while currentNode is not None:
            prevNode = currentNode
            if currentNode.value > node.value:
                currentNode = currentNode.left
            else:
                currentNode = currentNode.right
            if prevNode.value > node.value:
                prevNode.left = node
            else:
                prevNode.right = node
    def getTreeRoot(self):
        return self.root

接着递归查询二叉树中每一个的高度，如果左右子树的高度差超过1，那么二叉树就是不平衡的。
computeTreeHeight()是递归计算节点的左右子树的高度，当传入的节点是None时，返回高度0，否则递归调用自己去计算该节点的左右子树的高度。

class BalancedTree:
    def __init__(self):
        self.balanced = True
    def isTreeBalanced(self, node):
        self.computeTreeHeight(node)
        return self.balanced
    def computeTreeHeight(node):
        if node is null:
            return 0
        leftHeight = computeTreeHeight(node.left)
        rightHeight = computeTreeHeight(node.right)
        if abs(leftHeight - rightHeight) > 1:
            self.balanced = False
        height = 0
        if leftHeight > rightHeight :
            height = leftHeight
        else:
            height = rightHeight
        print("node value:{0}, left height:{1}, right height:{2}, height{}".format(node.value,leftHeight,rightHeight,height+1))
        return height + 1

构造一棵二叉树，调用上面代码判断二叉树的平衡性：

array = [6,4,9,2,5,7,10,1,3,8]
util = TreeUtil()
for node in array:
    n = TreeNode(node)
    util.addTreeNode(n)
root = util.getTreeRoot()
bt = BalancedTree()
isBalanced = bt.isTreeBalanced(root)
if isBalanced:
    print(" the binary tree is balaced")
else:
    print(" the binary tree is not balanced") 

运行结果为：
二叉树为：

image.png

image.png