平衡樹：二叉樹的每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差不超過(guò)1.

• 如果一個(gè)二叉樹是空的匙握，那么其高度為0咆槽；
• 如果一個(gè)二叉樹的只有一個(gè)節(jié)點(diǎn)，那么其高度為1肺孤；
• 對(duì)于非葉子節(jié)點(diǎn)的二叉樹罗晕，其高度為左子樹與右子樹高度的最大值
  二叉樹的高度可以用遞歸算法來(lái)實(shí)現(xiàn)：
• 如果輸入的是空節(jié)點(diǎn)济欢，高度為0赠堵；
• 如果輸入的是葉子節(jié)點(diǎn)小渊，左右子樹都為空，則其高度為1茫叭；
• 如果輸入的是非葉子節(jié)點(diǎn)酬屉，那么分別計(jì)算左右子樹的高度，選取最大值加1揍愁，即為二叉樹的高度呐萨。
  樹的節(jié)點(diǎn)實(shí)現(xiàn)
  定義二叉樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，其包含value以及左孩子與右孩子

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

排序樹的實(shí)現(xiàn)：
構(gòu)建排序二叉樹莽囤，創(chuàng)建TreeUtil類谬擦，當(dāng)加入節(jié)點(diǎn)的值比當(dāng)前節(jié)點(diǎn)小，則進(jìn)入左子樹朽缎，當(dāng)加入節(jié)點(diǎn)值比當(dāng)前節(jié)點(diǎn)大惨远，則進(jìn)入右子數(shù)。
向排序樹中添加葉子節(jié)點(diǎn)函數(shù)為 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

接著遞歸查詢二叉樹中每一個(gè)的高度话肖，如果左右子樹的高度差超過(guò)1北秽，那么二叉樹就是不平衡的。
computeTreeHeight()是遞歸計(jì)算節(jié)點(diǎn)的左右子樹的高度最筒，當(dāng)傳入的節(jié)點(diǎn)是None時(shí)贺氓，返回高度0，否則遞歸調(diào)用自己去計(jì)算該節(jié)點(diǎn)的左右子樹的高度床蜘。

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

構(gòu)造一棵二叉樹辙培，調(diào)用上面代碼判斷二叉樹的平衡性：

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") 

運(yùn)行結(jié)果為：
二叉樹為：

image.png

image.png