平衡二叉树

平衡二叉树的定义:
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定.
问题1:
把一个升序的数组转换成平衡二叉树
对一个二叉搜索树进行中序遍历就可以得到一个升序的数组,那么反过来考虑,数组的中值即为root,然后数组分为左子树和右子树,继续进行递归即可得出结果.

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None

        mid = len(nums) // 2

        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

问题2:
给一个二叉树,判断是否是平衡树
首先写计算二叉树高度的函数
树的高度 = max(左子树高度，右子树高度)+1

def getHeight(self, root):
    if not root:
        return 0

    return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

可以得到高度后对树递归求解每个节点的左右子树的高度差，如果有大于1的，则return False

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True

        return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)