【剑指offer】 平衡二叉树（python）

相关知识点：

一棵树是平衡二叉树，必须满足两个条件：

1、该二叉树首先是二叉搜索树，即当前节点的值大于左节点的值，并且当前节点的值大于右节点的值。

2、左子树和右子树的高度差的绝对值不大于1。

解题思路：

通过两个内置函数对二叉树进行判定，判断是否满足上述两个条件。

下面是示例代码：

# -*- coding:utf-8 -*-
'''
平衡二叉树：
1、左子树和右子树的高度差的绝对值不大于1
2、满足搜索树的条件

python可以返回一个或多个参数，但是
在一个函数中，必须设置python返回的
参数数目相同。


'''
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if pRoot == None:
            return True
        # 判断二叉树是否是搜索树
        def Is_SearchTree(pRoot):
            if pRoot.left != None and pRoot.val > pRoot.left.val:
                return False
            if pRoot.right != None and pRoot.val < pRoot.right.val:
                return False
        # 判断搜索树是否是平衡树
        def calc_height(pRoot):
            # 初始条件应该为判断为空，返回0
            if pRoot == None:
                return 0
            Is_SearchTree(pRoot)
            L = calc_height(pRoot.left)
            R = calc_height(pRoot.right)
            return max(L, R) + 1
        # 增加求绝对值的操作
        margin = abs(calc_height(pRoot.left) - calc_height(pRoot.right))
        if margin > 1:
            return False
        # 递归对当前节点的左右子树进行判断，判定是否为平衡二叉树
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)