学步园

        判断一棵树是否平衡，需要注意的是和判断一棵树是否为平衡二叉树的区别。 平衡二叉树的定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1， 并且左右两个子树都是一 棵平衡二叉树。 此时指的是这棵树任意两个叶子结点到根结点的距离之差不大于1。

节点定义为：

struct Node{
    int key;
    Node *lchild, *rchild, *parent;
};

只需要求出离根结点最近和最远的叶子结点，然后看它们到根结点的距离之差是否大于1即可。

void getDepth(Node *head){
    if(head == NULL) return;
    ++d;
    getDepth(head->lchild);
    if(head->lchild == NULL && head->rchild == NULL)
        dep[num++] = d;
    getDepth(head->rchild);
    --d;
}

求出所有叶子结点到根结点的距离后，再求出其中的最大值和最小值， 然后作差与1比较即可。此外，空树认为是平衡的。代码如下：

bool isBalance(Node *head){
    if(head == NULL) return true;
    getDepth(head);
    int max = dep[0], min = dep[0];
    for(int i=0; i<num; ++i){
        if(dep[i]>max) max = dep[i];
        if(dep[i]<min) min = dep[i];
    }
    if(max-min > 1) return false;
    else return true;
}