考研笔记

板子：判断完全二叉树与平衡二叉树

完全二叉树：层序遍历，空孩子也入队；碰到第一个空结点以后，后面不能再出现非空结点。 平衡二叉树：后序求树高，用 表示「已经不平衡」，一趟就能判断完。

代码

bool isComplete(BiTree T) {                  // 判断完全二叉树
    BiTNode *q[MaxSize];                     // 空孩子也要入队，队列要开到 2n+1
    int front = 0, rear = 0;
    if (T == NULL) return true;              // 空树算完全二叉树
    q[rear++] = T;
    while (front < rear) {
        BiTNode *p = q[front++];
        if (p != NULL) {                     // 非空结点：左右孩子不管空不空都入队
            q[rear++] = p->lchild;
            q[rear++] = p->rchild;
        } else {                             // 碰到第一个空结点：后面必须全是空
            while (front < rear)
                if (q[front++] != NULL) return false;   // 空结点后面还有非空结点：不是完全二叉树
        }
    }
    return true;
}
 
int balHeight(BiTree T) {                    // 平衡时返回树高，不平衡时返回 -1
    if (T == NULL) return 0;
    int hl = balHeight(T->lchild);
    if (hl == -1) return -1;                 // 左子树已经不平衡：直接往上报，不用再算
    int hr = balHeight(T->rchild);
    if (hr == -1) return -1;
    if (hl - hr > 1 || hr - hl > 1) return -1;   // 自己不平衡：左右高度差超过 1
    return (hl > hr ? hl : hr) + 1;
}
 
bool isBalanced(BiTree T) {
    return balHeight(T) != -1;
}

复杂度：两个都是时间 。isComplete 空间 ，isBalanced 空间 。

关键边界

位置为什么
空孩子也入队完全二叉树按层序排列时，前面没有空位。把空位也放进队列，才能检查「空位后面还有没有结点」
队列开到 个结点加上 个空指针，一共 次入队，而且不是循环队列
balHeight 用 表示不平衡高度不可能是负数，所以 不会和正常高度混淆。这样一趟后序就能同时算高度、判平衡

易错点

  • 平衡的判断看的是每一个结点，不是只看根。根的左右子树一样高，但子树内部不平衡，也不是平衡二叉树。
  • 如果对每个结点都单独调用 Height 求左右高度再比较，时间会退化到 。教材上用两个引用参数（balance 和 h）同时带回两个结果，和这里用 的写法等价。
  • 「平衡二叉树」只要求高度差不超过 1，不要求是二叉排序树。如果题目要判断 AVL，就要再加上 判断 BST。

链接

反向链接