平衡二叉树（AVL树）

1.空树是平衡二叉树。
2.如果一棵树不为空，并且其中所有的字数都满足各自的左子树和右子树高度差不超过1.

判断是否为平衡二叉树

思路：需要辅助函数来求出树的深度。遍历每一个节点，同时判断每一个节点的左右子树的深度差即可完成平衡二叉树的判别。（考点：树的遍历，树的深度）

#求树的深度递归求法
def depth(root):
    if not root:
        return 0
    left = self.depth(root.left)
    right = self.depth(root.right)
    return left+1 if left>right else right+1

完整代码为

# -*- coding:utf-8 -*-

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class CheckBalance:
    def __init__(self):
        self.flag = True
    def check(self, root):
        # write code here
        if not root:
            return
        left = self.depth(root.left)
        right = self.depth(root.right)
        if abs(left-right)>1:
            self.flag = False
        self.check(root.left)
        self.check(root.right)
        return self.flag

    def depth(self,root):
        if not root:
            return 0
        left = self.depth(root.left)
        right = self.depth(root.right)
        return left+1 if left>right else right+1

满二叉树

满二叉树是除了最后一层的节点无任何子节点外，剩下的每一层上的节点都有两个子节点。

完全二叉树

设二叉树的深度为h，出第h层外，其他各层（1~h-1）的节点数都达到最大个数，第h层所有的节点都集中在最左边。

我的思路：将二叉树书序列化，判断空节点会否出现在中间位置。

bat算法精讲思路：
1.采用按层遍历二叉树的形式，从每层的左边向右边一次遍历所有的节点。
2.如果一个节点只有右孩子没有左孩子，则直接返回false。
3.如果该节点只有左孩子，那么之后的节点都必须为叶子节点。

搜索二叉树

每棵子树的头结点都比各自左子树上的节点值大，也都比各自右子树节点值小。
####特点：搜索二叉树按照中序遍历得到的序列，一定是从小到大排列的。
红黑树、平衡二叉树等，其实都是搜索二叉树的不同实现。