Day12

昨天写的博客忘了点击“发布”，对于苛求完美的我来说好难过呀。

108. Convert Sorted Array to Binary Search Tree
     **思路：首先都不记得什么是平衡二叉树。左右子节点高度相差不能超过1。那就从序列的中间数作为根节点摆放。递归下去，两边一定会平衡的。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if len(nums) == 0:
            return None
        if len(nums) == 1:
            return TreeNode(nums[0])
        
        root = TreeNode(nums[len(nums)/2])
        root.left = self.sortedArrayToBST(nums[0:len(nums)/2])
        root.right = self.sortedArrayToBST(nums[len(nums)/2+1:])
        
        return root

110. Balanced Binary Tree
     **思路：真的不会写递归，判断两个子节点的高度是否相差小于1，再递归到各自的子节点，一层递归。二层递归是子二叉树的高度值，又用了一个递归，判断两边的高度的最大值+1

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def height(self,root):
        if root == None:
            return 0
        return max(self.height(root.left),self.height(root.right))+1
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root == None:
            return True
        if abs(self.height(root.left) - self.height(root.right)) <=1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        else:
            return False