考研笔记

板子：靠递归返回值的题（树高、结点数、叶子数……）

套路就两句话：① 空树返回什么；② 拿到左右子树的答案以后，怎么算出整棵树的答案。这两句想清楚了，代码就是三四行。

代码

int Height(BiTree T) {                       // 树高：空树为 0，只有根为 1
    if (T == NULL) return 0;
    int hl = Height(T->lchild);              // 先把左右子树的高度存下来
    int hr = Height(T->rchild);
    return (hl > hr ? hl : hr) + 1;          // 较高的那棵 + 根这一层
}
 
int CountNodes(BiTree T) {                   // 结点总数
    if (T == NULL) return 0;
    return CountNodes(T->lchild) + CountNodes(T->rchild) + 1;   // 左 + 右 + 根
}
 
int CountLeaves(BiTree T) {                  // 叶子数（度为 0 的结点）
    if (T == NULL) return 0;
    if (T->lchild == NULL && T->rchild == NULL) return 1;       // 自己就是叶子
    return CountLeaves(T->lchild) + CountLeaves(T->rchild);
}
 
int CountDeg2(BiTree T) {                    // 度为 2 的结点数
    if (T == NULL) return 0;
    int self = (T->lchild != NULL && T->rchild != NULL) ? 1 : 0;       // 根自己算不算
    return CountDeg2(T->lchild) + CountDeg2(T->rchild) + self;
}
 
int CountDeg1(BiTree T) {                    // 度为 1 的结点数
    if (T == NULL) return 0;
    int self = ((T->lchild == NULL) != (T->rchild == NULL)) ? 1 : 0;   // 两个孩子恰好一空一不空
    return CountDeg1(T->lchild) + CountDeg1(T->rchild) + self;
}
 
int CountLevelK(BiTree T, int k) {           // 第 k 层的结点数（根在第 1 层）
    if (T == NULL) return 0;
    if (k == 1) return 1;                    // 已经走到第 k 层：当前结点算一个
    return CountLevelK(T->lchild, k - 1) + CountLevelK(T->rchild, k - 1);   // 往下一层，k 减 1
}
 
void SwapChildren(BiTree T) {                // 交换所有结点的左右子树（镜像）
    if (T == NULL) return;
    BiTNode *t = T->lchild; T->lchild = T->rchild; T->rchild = t;
    SwapChildren(T->lchild);
    SwapChildren(T->rchild);
}

复杂度：每个结点访问一次，时间 ，空间 。

两句话对照

题目① 空树返回② 怎么合并
树高0左右
结点数0左 + 右 + 1
叶子数0自己是叶子就返回 1，否则 左 + 右
度为 2 / 度为 10左 + 右 + 自己算不算
第 层0 时返回 1，否则 左() + 右()

CountLevelK 的 k 是参数往下传（前序的思路），其他几个都是返回值往上交（后序的思路）。

易错点

  • 树高的口径：这里空树高度为 0、只有根的树高度为 1（根在第 1 层），和教材一致。
  • 判断叶子要左右孩子都为空，只判断一个就错了。
  • 求树高时，先用 hl、hr 把结果存下来再比较。写成 Height(l) > Height(r) ? Height(l) + 1 : Height(r) + 1 会让每一层都重复递归，时间变成指数级。
  • 自查：任何二叉树都满足 ，写完可以拿来验证叶子数和度为 2 的结点数。

链接

反向链接