考研笔记

板子：找祖先与最近公共祖先

两个都是后序的思路：先问左右子树「你那边有没有要找的结点」，再根据两边的回答决定自己怎么做。

代码

bool printAncestors(BiTree T, int x) {       // 输出值为 x 的结点的所有祖先（从下往上）；找到了返回 true
    if (T == NULL) return false;
    if (T->data == x) return true;           // 找到 x 本身：不输出它，只往上报「找到了」
    if (printAncestors(T->lchild, x) || printAncestors(T->rchild, x)) {
        printf("%d ", T->data);              // x 在我的子树里，所以我是它的祖先
        return true;
    }
    return false;
}
 
BiTNode *LCA(BiTree T, BiTNode *p, BiTNode *q) {   // p、q 的最近公共祖先（p、q 都在树里）
    if (T == NULL || T == p || T == q) return T;   // 空树返回 NULL；碰到 p 或 q 就返回它自己
    BiTNode *l = LCA(T->lchild, p, q);       // 左子树里找到的结果
    BiTNode *r = LCA(T->rchild, p, q);       // 右子树里找到的结果
    if (l != NULL && r != NULL) return T;    // p、q 一个在左一个在右：T 就是分叉点
    return l != NULL ? l : r;                // 都在同一边：把那一边的结果往上交
}
 
int lcaSeq(int i, int j) {                   // 顺序存储（下标从 1）：编号 i、j 的最近公共祖先
    while (i != j) {
        if (i > j) i /= 2;                   // 编号大的深度不会更小，让它先跳到双亲
        else j /= 2;
    }
    return i;
}

复杂度：前两个都是时间 、空间 ；顺序存储版时间 、空间 。

关键边界

情况结果为什么
p 是 q 的祖先返回 p碰到 p 就直接返回了，不会再往下找 q
顺序存储下标从 1双亲是 i / 2下标从 0 时双亲是 (i - 1) / 2，代码要跟着改
printAncestors 的输出顺序从下往上递归回来时才输出。想要从上往下，就用后序非递归：访问到 时，栈里从底到顶就是它的祖先

易错点

  • printAncestors 默认值为 的结点只有一个。有重复值时，只会找到其中一个。
  • LCA 比较的是结点指针，不是 data。
  • lcaSeq 不能写成两个数同时除以 2，那样可能直接跳过它们的公共祖先。

链接

反向链接