考研笔记

板子：用前序 + 中序建树

前序的第一个元素是根；在中序里找到根，根的左边是左子树，右边是右子树。数出左子树有 len 个结点，就能在前序里划出左右子树的范围，然后递归。

代码

BiTree build(int pre[], int pl, int pr, int in[], int il, int ir) {   // 用 pre[pl..pr] 和 in[il..ir] 建树
    if (pl > pr) return NULL;                // 区间为空：空树
    BiTNode *T = (BiTNode *)malloc(sizeof(BiTNode));
    T->data = pre[pl];                       // 前序的第一个就是根
    int k = il;
    while (in[k] != pre[pl]) k++;            // 在中序里找到根的位置 k
    int len = k - il;                        // 左子树的结点个数
    T->lchild = build(pre, pl + 1, pl + len, in, il, k - 1);       // 前序里根后面的 len 个是左子树
    T->rchild = build(pre, pl + len + 1, pr, in, k + 1, ir);       // 再往后的都是右子树
    return T;
}
// 调用：BiTree T = build(pre, 0, n - 1, in, 0, n - 1);

复杂度：每层在中序里线性查找根，最坏时间 。先用一个数组记下每个值在中序里的下标，可以降到 。空间 。

关键边界：三个序列的区间怎么划分

序列左子树根右子树
前序 prepl+1 ~ pl+lenplpl+len+1 ~ pr
中序 inil ~ k-1kk+1 ~ ir
后序 post（变形）pl ~ pl+len-1prpl+len ~ pr-1

记法：len 只能从中序里算出来（k - il），前序和后序都靠 len 来切分。

后序 + 中序：根是 post[pr]，左右子树按上表第三行切分，代码只需要改两行递归调用。

易错点

  • 前序里左子树的范围是 pl + 1 到 pl + len，不是到 k。k 是中序的下标，不能拿来算前序的范围。
  • 要求结点的值互不相同，否则在中序里找根可能找错。
  • 前序 + 后序不能唯一确定一棵二叉树（只有一个孩子时分不清是左孩子还是右孩子）。必须有中序。

链接

反向链接