Problem F: 判断平衡二叉树*

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：76 Solved：36

Description

平衡二叉查找树：简称平衡二叉树。由前苏联的数学家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉树，根据科学家的英文名也称为AVL树。它具有如下几个性质：

可以是空树。

假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1

平衡之意，如天平，即两边的分量大约相同。如定义，假如一棵树的左右子树的高度之差超过1，如左子树的树高为2，右子树的树高为0，子树树高差的绝对值为2就打破了这个平衡。如依次插入1，2，3三个结点（如下图）后，根结点的右子树树高减去左子树树高为2，树就失去了平衡。                                                                                                                                                                                                                                         

        

给定一前序二叉树的数据，请构造根节点为 root 的二叉树，输出这棵树是否为平衡二叉树。

Input

输入为一棵树的先序遍历序列，遇到不存在的子节点用0表示。输入的结尾为-1。

Output

如果是平衡二叉树，则返回true，否则返回false。

Sample Input Copy 

4 2 1 0 0 3 0 0 6 5 0 0 0 -1

Sample Output Copy 

true

HINT

树的深度最多为19层。