第4章树与二叉树算法

旧版讲义 · 校订增强 · 专题阅读 · 保留代码与校订注 · 与版本锁一致

第4章树与二叉树算法¶

做题总路线与存储口径¶

树算法题怎样从题意反推出遍历顺序？¶

何时用：所有二叉树、普通树与森林的算法设计题。

思路步骤：

先确认存储结构：二叉链表、顺序存储、孩子兄弟表示还是双亲数组。
再问当前结点的处理是否依赖子树结果：不依赖可先序；依赖左右结果用后序；利用 BST 有序性用中序；涉及层、最短边数或完全性用层序。
写出空结点出口，再把“处理当前结点”的 visit 填入正确位置。
若递归返回值不足以完成输出/初始化，再增加主函数；不要一开始就堆全局变量。
最后核对树高、深度、根下标、空结点标记等题目口径。

伪代码/关键模板：

存储结构 → 可访问的邻接关系
是否依赖子树结果 → 先序 / 中序 / 后序
是否依赖层次       → BFS
空树出口 → 递归子问题 → visit/合并返回值

复杂度：遍历所有结点通常为 O(n)；递归额外空间 O(h)，最坏 O(n)。

易错边界：旧版说树题“不必考虑优化”只是应试建议，不代表可以漏写复杂度；递归遍历必须说明最坏栈深；同一题的“高度”和“深度”起点可能分别从 1 或 0 计数。

回源 · PDF 第 107 页 · b_107_0；PDF 第 107 页 · b_107_1；PDF 第 107 页 · b_107_2；PDF 第 111 页 · b_111_3；PDF 第 111 页 · b_111_4

四种树结构的孩子下标或指针怎样快速对齐？¶

何时用：题目在二叉链表、顺序二叉树、孩子兄弟表示和双亲数组之间切换时。

思路步骤：

二叉链表：left/right 直接访问左右子树。
0 下标顺序树：结点 i 的孩子为 2i+1、2i+2；1 下标则为 2i、2i+1。
孩子兄弟表示：first_child 相当于左孩子，next_sibling 相当于右孩子。
双亲数组：parent[i] 指向代表元或父结点，适合并查集。
稀疏顺序树必须有空位标记并检查数组边界。

伪代码/关键模板：

typedef struct ACTreeNode {
    int data;
    int weight;
    struct ACTreeNode *left;
    struct ACTreeNode *right;
} ACTreeNode;

typedef struct ACGeneralNode {
    int data;
    struct ACGeneralNode *first_child;
    struct ACGeneralNode *next_sibling;
} ACGeneralNode;

enum { AC_MAXV = 128 };

typedef struct ACSeqTree {
    int node[AC_MAXV];
    int elem_num;
} ACSeqTree;

复杂度：已知结点时，链式孩子访问与顺序下标计算均为 O(1)；寻找双亲是否 O(1) 取决于结构。

易错边界：0/1 下标公式不可混用；顺序存储中 elem_num 是已占用数组范围，不一定等于非空结点数；孩子兄弟表示中的 next_sibling 不是该结点的孩子。

回源 · PDF 第 107 页 · b_107_4；PDF 第 107 页 · b_107_5；PDF 第 107 页 · b_107_7；PDF 第 107 页 · b_107_12；PDF 第 107 页 · b_107_13；PDF 第 108 页 · b_108_0；PDF 第 108 页 · b_108_2

递归遍历与信息流¶

先序、中序、后序的共同骨架是什么？¶

何时用：二叉树需要访问每个结点一次，且题目没有强制非递归实现。

思路步骤：

空指针立即返回。
把“访问根、递归左、递归右”看成三个原子任务。
根在两次递归前是先序，中间是中序，最后是后序。
visit 若会失败，应让失败状态向上短路传播，而不是继续无意义遍历。

伪代码/关键模板：

void ac_preorder(const ACTreeNode *p, void (*visit)(const ACTreeNode *)) {
    if (p == NULL) return;
    visit(p);
    ac_preorder(p->left, visit);
    ac_preorder(p->right, visit);
}

void ac_inorder(const ACTreeNode *p, void (*visit)(const ACTreeNode *)) {
    if (p == NULL) return;
    ac_inorder(p->left, visit);
    visit(p);
    ac_inorder(p->right, visit);
}

void ac_postorder(const ACTreeNode *p, void (*visit)(const ACTreeNode *)) {
    if (p == NULL) return;
    ac_postorder(p->left, visit);
    ac_postorder(p->right, visit);
    visit(p);
}

复杂度：时间 O(n)，递归栈 O(h)，最坏 O(n)。

易错边界：三个函数的唯一区别是 visit 的位置；函数名、左右孩子字段要统一；极度退化树可能使递归栈过深，工程环境需考虑显式栈。

回源 · PDF 第 109 页 · b_109_0；PDF 第 109 页 · b_109_1；PDF 第 109 页 · b_109_9；PDF 第 109 页 · b_109_11；PDF 第 109 页 · b_109_13；PDF 第 109 页 · b_109_16；PDF 第 110 页 · b_110_1

孩子兄弟表示下，先根与后根遍历怎样还原？¶

何时用：普通树或森林采用 first_child/next_sibling 存储。

思路步骤：

把 first_child 看作二叉树左指针，next_sibling 看作右指针。
先根遍历：先访问当前结点，再遍历其第一个孩子所代表的孩子森林，最后遍历兄弟。
后根遍历：先处理所有孩子，再访问当前结点，最后处理兄弟。
森林的兄弟链由同一递归自然覆盖，不要在外层重复扫描同一棵树。

伪代码/关键模板：

void ac_tree_preorder(const ACGeneralNode *p, void (*visit)(const ACGeneralNode *)) {
    if (p == NULL) return;
    visit(p);
    ac_tree_preorder(p->first_child, visit);
    ac_tree_preorder(p->next_sibling, visit);
}

void ac_tree_postroot(const ACGeneralNode *p, void (*visit)(const ACGeneralNode *)) {
    if (p == NULL) return;
    ac_tree_postroot(p->first_child, visit);
    visit(p);
    ac_tree_postroot(p->next_sibling, visit);
}

复杂度：时间 O(n)，递归栈最坏 O(n)。

易错边界：后根遍历等价于对应二叉树的中序，不是二叉树后序；visit 必须放在孩子递归之后、兄弟递归之前。

回源 · PDF 第 110 页 · b_110_3；PDF 第 110 页 · b_110_4；PDF 第 110 页 · b_110_5；PDF 第 110 页 · b_110_8；PDF 第 110 页 · b_110_10；PDF 第 111 页 · b_111_0

怎样用“是否依赖子树结果”选择遍历？¶

何时用：叶子计数、BST 判断、求高度、表达式输出、完全二叉树判断等混合题型。

思路步骤：

只检查当前结点属性：任一深度优先次序都可，优先先序。
当前结果依赖左右子树高度/真假：后序返回并合并。
需要有序访问 BST：中序，并保存上一访问值。
要把中缀表达式按运算结构输出：中序并在子表达式外加括号。
需要逐层或第一次到达最短：层序队列。

伪代码/关键模板：

visit(p) 不依赖孩子 → 根可先处理
visit(p) = f(left_result, right_result) → 后序
依赖 BST 有序序列 → 中序
依赖层号/宽度/最短边数 → BFS

复杂度：只遍历一遍通常 O(n)；空间为 DFS 的 O(h) 或 BFS 队列的 O(n)。

易错边界：能用某种遍历不等于它最容易证明；求“结点深度”可自顶向下传参，求“子树高度”更适合自底向上返回。

回源 · PDF 第 111 页 · b_111_12；PDF 第 111 页 · b_111_13；PDF 第 111 页 · b_111_15；PDF 第 112 页 · b_112_0；PDF 第 112 页 · b_112_2；PDF 第 112 页 · b_112_4；PDF 第 112 页 · b_112_6

全局变量与递归返回值，什么时候各自更合适？¶

何时用：遍历中需要累计总和/计数，或父结点必须消费子树结果时。

思路步骤：

全局累加适合“每命中一个结点就收集一次”，如叶子数、WPL。
返回值适合“以当前结点为根的子问题答案”，如高度、是否平衡、子树权重和。
优先通过参数或返回值保持函数可重入；全局变量必须在每次主调用前重置。
需要同时返回高度与合法性时，可用特殊值、结构体或输出参数。

伪代码/关键模板：

collect(p, shared_state)       // 自顶向下收集
left  = solve(p->left)
right = solve(p->right)
return combine(p,left,right)  // 自底向上合并

复杂度：两种方式都可保持 O(n)；返回值不额外增加渐进空间。

易错边界：全局变量未重置会污染下一组测试；返回特殊值必须与合法结果域区分；不要既全局累计又把同一量向上返回造成重复计算。

回源 · PDF 第 112 页 · b_112_9；PDF 第 112 页 · b_112_17；PDF 第 112 页 · b_112_18；PDF 第 113 页 · b_113_0；PDF 第 113 页 · b_113_2；PDF 第 114 页 · b_114_9；PDF 第 114 页 · b_114_10；PDF 第 115 页 · b_115_1；PDF 第 115 页 · b_115_3

树性质判断：用返回值携带证明¶

二叉树高度为什么是最典型的后序返回题？¶

何时用：求树高，约定空树高为 0、只有根结点高为 1。

思路步骤：

空树返回 0。
递归得到左、右子树高度。
当前高度为 max(left,right)+1。
根调用的返回值就是整棵树高度。

伪代码/关键模板：

int ac_tree_height(const ACTreeNode *p) {
    if (p == NULL) return 0;
    int left = ac_tree_height(p->left);
    int right = ac_tree_height(p->right);
    return (left > right ? left : right) + 1;
}

复杂度：时间 O(n)，递归栈 O(h)。

易错边界：不要把“根深度为 0”的 WPL 口径混到“根高度为 1”；每棵子树只计算一次，若反复调用 height 判断平衡会退化为 O(n²)。

回源 · PDF 第 125 页 · b_125_0；PDF 第 125 页 · b_125_1；PDF 第 125 页 · b_125_2；PDF 第 125 页 · b_125_3；PDF 第 125 页 · b_125_4；PDF 第 125 页 · b_125_7

判断完全二叉树，遇到第一个空缺后要保持什么状态？¶

何时用：链式二叉树判断是否完全，或顺序树检查有效结点是否形成无空洞前缀。

思路步骤：

层序扫描，gap=false。
按左、右孩子顺序检查。
一旦某个孩子为空就令 gap=true。
gap 之后若再遇到任何非空孩子，立即返回 false。
顺序存储版本等价于检查最后一个非空位置之前没有空洞。

伪代码/关键模板：

int ac_is_complete_tree(const ACTreeNode *root) {
    if (root == NULL) return 1;
    const ACTreeNode *queue[AC_MAXV];
    int front = 0, rear = 0, gap = 0;
    queue[rear++] = root;
    while (front < rear) {
        const ACTreeNode *p = queue[front++];
        if (p->left != NULL) {
            if (gap || rear >= AC_MAXV) return 0;
            queue[rear++] = p->left;
        } else {
            gap = 1;
        }
        if (p->right != NULL) {
            if (gap || rear >= AC_MAXV) return 0;
            queue[rear++] = p->right;
        } else {
            gap = 1;
        }
    }
    return 1;
}

复杂度：时间 O(n)，队列空间 O(n)。

易错边界：有右孩子无左孩子必须失败；标志应在第一次缺孩子时设置；固定数组实现要检查队列容量。

回源 · PDF 第 116 页 · b_116_14；PDF 第 116 页 · b_116_15；PDF 第 116 页 · b_116_16；PDF 第 116 页 · b_116_18；PDF 第 116 页 · b_116_19；PDF 第 116 页 · b_116_20；PDF 第 117 页 · b_117_0

判断 BST，为什么不能把前驱初值直接设为 INT_MIN？¶

何时用：结点值为 int、BST 定义要求左<根<右且不允许重复。

思路步骤：

中序遍历产生应当严格递增的序列。
用 has_previous 区分“尚无前驱”，避免拿某个合法 int 当哨兵。
首次访问只记录；之后若 current≤previous 就失败。
左子树失败后立即短路，不再访问根和右子树。

伪代码/关键模板：

int ac_bst_inorder_check(
    const ACTreeNode *p, int *has_previous, int *previous
) {
    if (p == NULL) return 1;
    if (!ac_bst_inorder_check(p->left, has_previous, previous)) return 0;
    if (*has_previous && p->data <= *previous) return 0;
    *previous = p->data;
    *has_previous = 1;
    return ac_bst_inorder_check(p->right, has_previous, previous);
}

int ac_is_bst(const ACTreeNode *root) {
    int has_previous = 0, previous = 0;
    return ac_bst_inorder_check(root, &has_previous, &previous);
}

复杂度：时间 O(n)，递归栈 O(h)。

易错边界：新版补充/校订：旧版建议 previous=INT_MIN，若首结点本身是 INT_MIN 会误判；应另设 has_previous。若题目允许重复，比较符号须按其 BST 定义调整。

回源 · PDF 第 117 页 · b_117_1；PDF 第 117 页 · b_117_2；PDF 第 117 页 · b_117_3；PDF 第 117 页 · b_117_4；PDF 第 117 页 · b_117_7；PDF 第 117 页 · b_117_8

AVL 判断怎样在一次后序中同时返回高度与失败状态？¶

何时用：判断二叉树任意结点左右子树高度差是否不超过 1。

思路步骤：

空树高度返回 0。
递归求左高；若为 -1，立即传播失败。
递归求右高；同样短路。
高度差绝对值大于 1 返回 -1，否则返回 max+1。
根返回值不为 -1 即平衡。

伪代码/关键模板：

int ac_avl_height_or_fail(const ACTreeNode *p) {
    if (p == NULL) return 0;
    int left = ac_avl_height_or_fail(p->left);
    if (left < 0) return -1;
    int right = ac_avl_height_or_fail(p->right);
    if (right < 0) return -1;
    int diff = left - right;
    if (diff < -1 || diff > 1) return -1;
    return (left > right ? left : right) + 1;
}

int ac_is_avl(const ACTreeNode *root) {
    return ac_avl_height_or_fail(root) >= 0;
}

复杂度：每个结点一次，时间 O(n)，递归栈 O(h)。

易错边界：不要对每个结点重新求左右高度，否则最坏 O(n²)；-1 必须不属于合法高度域；若题目还要求 BST，需要另做有序性检查。

回源 · PDF 第 117 页 · b_117_15；PDF 第 117 页 · b_117_16；PDF 第 117 页 · b_117_17；PDF 第 118 页 · b_118_0

并查集怎样同时做路径压缩与按秩合并？¶

何时用：动态合并集合、判断两点连通、Kruskal 判环、统计连通分量。

思路步骤：

初始化 parent[i]=i、rank[i]=0。
find 递归找到根，并把沿途结点直接挂到根。
union 先找两个根；相同则无需合并。
把矮树挂到高树；同高时任选一方为根并提升其秩。

伪代码/关键模板：

typedef struct ACDSU {
    int parent[AC_MAXV];
    unsigned char rank[AC_MAXV];
    int n;
} ACDSU;

void ac_dsu_init(ACDSU *dsu, int n) {
    dsu->n = n;
    for (int i = 0; i < n; ++i) {
        dsu->parent[i] = i;
        dsu->rank[i] = 0;
    }
}

int ac_dsu_find(ACDSU *dsu, int x) {
    if (dsu->parent[x] != x) {
        dsu->parent[x] = ac_dsu_find(dsu, dsu->parent[x]);
    }
    return dsu->parent[x];
}

int ac_dsu_union(ACDSU *dsu, int x, int y) {
    int rx = ac_dsu_find(dsu, x), ry = ac_dsu_find(dsu, y);
    if (rx == ry) return 0;
    if (dsu->rank[rx] < dsu->rank[ry]) dsu->parent[rx] = ry;
    else if (dsu->rank[rx] > dsu->rank[ry]) dsu->parent[ry] = rx;
    else {
        dsu->parent[ry] = rx;
        ++dsu->rank[rx];
    }
    return 1;
}

复杂度：路径压缩加按秩合并后，均摊单次近似 O(1)，严格为 O(α(n))；空间 O(n)。

易错边界：新版补充/校订：旧版只有路径压缩，本卡补充按秩合并；传入下标必须在 [0,n)；parent 数组未经初始化不能调用 find。

回源 · PDF 第 118 页 · b_118_2；PDF 第 118 页 · b_118_3；PDF 第 118 页 · b_118_7；PDF 第 118 页 · b_118_8；PDF 第 118 页 · b_118_9；PDF 第 119 页 · b_119_0；PDF 第 119 页 · b_119_1；PDF 第 119 页 · b_119_2

顺序与链式结构转换¶

完全二叉树数组怎样递归构造成二叉链表？¶

何时用：0 下标数组 A 存放 n 个完全二叉树结点，需要建立独立链式结点。

思路步骤：

当前数组下标 i≥n 时返回 NULL。
为 A[i] 分配结点，写入数据。
左孩子递归下标 2i+1，右孩子递归下标 2i+2。
任一分配失败时释放已经构造的部分并向上报告，避免返回半棵树。

伪代码/关键模板：

void ac_free_tree(ACTreeNode *p) {
    if (p == NULL) return;
    ac_free_tree(p->left);
    ac_free_tree(p->right);
    free(p);
}

ACTreeNode *ac_build_complete_rec(const int a[], int n, int i, int *ok) {
    if (i >= n) return NULL;
    ACTreeNode *p = malloc(sizeof(*p));
    if (p == NULL) {
        *ok = 0;
        return NULL;
    }
    p->data = a[i];
    p->weight = 0;
    p->left = ac_build_complete_rec(a, n, 2 * i + 1, ok);
    if (!*ok) {
        ac_free_tree(p->left);
        free(p);
        return NULL;
    }
    p->right = ac_build_complete_rec(a, n, 2 * i + 2, ok);
    if (!*ok) {
        ac_free_tree(p->left);
        ac_free_tree(p->right);
        free(p);
        return NULL;
    }
    return p;
}

ACTreeNode *ac_build_complete_tree(const int a[], int n) {
    if (a == NULL || n <= 0) return NULL;
    int ok = 1;
    ACTreeNode *root = ac_build_complete_rec(a, n, 0, &ok);
    return ok ? root : NULL;
}

复杂度：时间 O(n)，新建结点空间 O(n)，递归栈 O(log n)（完全二叉树）。

易错边界：数组从 A[0] 开始时才用 2i+1/2i+2；新版补充/校订：旧版未处理 malloc 失败，本卡保证失败时不泄漏已建子树。

回源 · PDF 第 119 页 · b_119_5；PDF 第 119 页 · b_119_6；PDF 第 119 页 · b_119_7；PDF 第 123 页 · b_123_5；PDF 第 123 页 · b_123_8；PDF 第 123 页 · b_123_9；PDF 第 123 页 · b_123_11；PDF 第 123 页 · b_123_12

二叉链表写回顺序数组，为什么必须先给出容量？¶

何时用：稀疏二叉树按 0 下标顺序位置写入数组，以 -1 表示空位。

思路步骤：

主函数先把容量 cap 内所有位置初始化为 -1。
根写到 0；结点 i 的左右孩子写到 2i+1、2i+2。
递归前检查目标下标是否小于 cap。
空子树无需继续向更深位置写 -1，因为数组已统一初始化。

伪代码/关键模板：

int ac_tree_to_seq_rec(const ACTreeNode *p, int out[], int cap, long long index) {
    if (p == NULL) return 1;
    if (index < 0 || index >= cap) return 0;
    out[index] = p->data;
    if (!ac_tree_to_seq_rec(p->left, out, cap, 2 * index + 1)) return 0;
    return ac_tree_to_seq_rec(p->right, out, cap, 2 * index + 2);
}

int ac_tree_to_seq(const ACTreeNode *root, int out[], int cap) {
    if (out == NULL || cap <= 0) return 0;
    for (int i = 0; i < cap; ++i) out[i] = -1;
    return ac_tree_to_seq_rec(root, out, cap, 0);
}

复杂度：初始化 O(cap)，遍历非空结点 O(n)，递归栈 O(h)。

易错边界：新版补充/校订：旧版递归直接写 B[i]，没有容量参数，稀疏深树可能越界；-1 只有在题目保证权值非负时才能作为空标记。

回源 · PDF 第 124 页 · b_124_0；PDF 第 124 页 · b_124_1；PDF 第 124 页 · b_124_2；PDF 第 124 页 · b_124_3；PDF 第 124 页 · b_124_4；PDF 第 124 页 · b_124_5；PDF 第 124 页 · b_124_6；PDF 第 124 页 · b_124_7

孩子兄弟树的“树的度”怎样在线性时间统计？¶

何时用：普通树采用 first_child/next_sibling，求所有结点孩子数的最大值。

思路步骤：

对当前结点沿孩子的兄弟链计数，得到当前结点的度。
对每个孩子递归求其子树最大度。
当前度与所有孩子子树结果取最大。
不要把当前结点自己的兄弟数误当成当前结点的度。

伪代码/关键模板：

int ac_general_tree_degree(const ACGeneralNode *root) {
    if (root == NULL) return 0;
    int degree = 0, best = 0;
    for (const ACGeneralNode *child = root->first_child;
         child != NULL;
         child = child->next_sibling) {
        ++degree;
        int child_best = ac_general_tree_degree(child);
        if (child_best > best) best = child_best;
    }
    return degree > best ? degree : best;
}

复杂度：每条孩子/兄弟边被常数次处理，时间 O(n)，递归栈 O(h)。

易错边界：叶结点度为 0；森林若由根的兄弟链表示，应对每棵根树分别取最大，不能把多棵树的根数当作某个结点的孩子数。

回源 · PDF 第 125 页 · b_125_8；PDF 第 125 页 · b_125_9；PDF 第 125 页 · b_125_10；PDF 第 125 页 · b_125_11；PDF 第 125 页 · b_125_12；PDF 第 126 页 · b_126_0；PDF 第 126 页 · b_126_2

镜像对称为何要同时递归两个位置？¶

何时用：判断二叉树是否关于根镜像对称。

思路步骤：

两个空结点对称；一空一非空不对称。
两个非空结点的数据必须相等。
p 的左子树与 q 的右子树镜像。
p 的右子树与 q 的左子树镜像。
根调用比较 root->left 与 root->right。

伪代码/关键模板：

int ac_mirror_pair(const ACTreeNode *p, const ACTreeNode *q) {
    if (p == NULL && q == NULL) return 1;
    if (p == NULL || q == NULL) return 0;
    if (p->data != q->data) return 0;
    return ac_mirror_pair(p->left, q->right)
        && ac_mirror_pair(p->right, q->left);
}

int ac_is_symmetric(const ACTreeNode *root) {
    return root == NULL || ac_mirror_pair(root->left, root->right);
}

复杂度：时间 O(n)，递归栈 O(h)。

易错边界：不能只比较同侧孩子；空树通常视为对称；短路与运算可在发现不对称后停止。

回源 · PDF 第 127 页 · b_127_4；PDF 第 127 页 · b_127_5；PDF 第 128 页 · b_128_1；PDF 第 128 页 · b_128_2；PDF 第 128 页 · b_128_3；PDF 第 128 页 · b_128_4；PDF 第 128 页 · b_128_5；PDF 第 128 页 · b_128_7；PDF 第 128 页 · b_128_8

代表题与统考真题¶

普通二叉树 LCA，若 p 或 q 不在树中该返回什么？¶

何时用：无父指针的一般二叉树，按结点地址求最低公共祖先。

思路步骤：

后序扫描左右子树。
当前结点等于 p/q 时，它可能就是祖先。
左右均返回候选时，当前结点是分叉处。
只有一侧有候选时向上返回该侧。
同时统计实际找到的目标数；目标缺失则返回 NULL。

伪代码/关键模板：

ACTreeNode *ac_lca_scan(
    ACTreeNode *root, const ACTreeNode *p, const ACTreeNode *q, int *found
) {
    if (root == NULL) return NULL;
    ACTreeNode *left = ac_lca_scan(root->left, p, q, found);
    ACTreeNode *right = ac_lca_scan(root->right, p, q, found);
    int self = root == p || root == q;
    if (self) ++*found;
    if (self || (left != NULL && right != NULL)) return root;
    return left != NULL ? left : right;
}

ACTreeNode *ac_lca(
    ACTreeNode *root, const ACTreeNode *p, const ACTreeNode *q
) {
    if (p == NULL || q == NULL) return NULL;
    int found = 0;
    ACTreeNode *candidate = ac_lca_scan(root, p, q, &found);
    int need = p == q ? 1 : 2;
    return found == need ? candidate : NULL;
}

复杂度：时间 O(n)，递归栈 O(h)。

易错边界：比较结点地址而不是 data；新版增强（按题设取舍）：若题设已保证 p、q 都在树中，旧版标准写法成立；本卡额外对缺失目标返回 NULL。p 是 q 的祖先时 LCA 可以是 p 自己。

回源 · PDF 第 128 页 · b_128_9；PDF 第 128 页 · b_128_10；PDF 第 128 页 · b_128_11；PDF 第 129 页 · b_129_0；PDF 第 129 页 · b_129_1；PDF 第 129 页 · b_129_2；PDF 第 129 页 · b_129_3；PDF 第 129 页 · b_129_5；PDF 第 129 页 · b_129_6；PDF 第 129 页 · b_129_8；PDF 第 129 页 · b_129_9

2014 WPL 怎样按定义一次递归求出？¶

何时用：二叉树叶结点含非负权值，根深度规定为 0，求所有叶结点 weight×depth 之和。

思路步骤：

把当前深度作为参数自顶向下传递。
空结点贡献 0。
叶结点贡献 weight×depth。
非叶结点返回左右子树 WPL 之和。
用独立整数 weight 字段和 long long 累计，不能拿字符 data 代替权值。

伪代码/关键模板：

long long ac_wpl(const ACTreeNode *p, int depth) {
    if (p == NULL) return 0;
    if (p->left == NULL && p->right == NULL) {
        return (long long)p->weight * depth;
    }
    return ac_wpl(p->left, depth + 1) + ac_wpl(p->right, depth + 1);
}

复杂度：时间 O(n)，递归栈 O(h)。

易错边界：根深度是 0；只有叶结点权值参与定义式；“所有非叶结点权值和”的推导只有在内部结点权值等于孩子权值和时才成立，不能无条件套用。

回源 · PDF 第 129 页 · b_129_10；PDF 第 129 页 · b_129_11；PDF 第 129 页 · b_129_12；PDF 第 129 页 · b_129_13；PDF 第 130 页 · b_130_0；PDF 第 130 页 · b_130_1；PDF 第 130 页 · b_130_2；PDF 第 130 页 · b_130_3；PDF 第 130 页 · b_130_8；PDF 第 130 页 · b_130_9；PDF 第 130 页 · b_130_11；PDF 第 130 页 · b_130_13；PDF 第 131 页 · b_131_0；PDF 第 131 页 · b_131_1

2017 表达式树输出中缀式，括号为什么排除根和叶？¶

何时用：表达式树结点保存操作数/运算符字符串，要求用括号反映原运算次序。

思路步骤：

中序递归自然给出“左表达式—根运算符—右表达式”。
非叶子子树表示一个复合表达式。
若该子树不是整棵树的根，在递归前后输出一对括号。
叶结点直接输出 data；一元运算结构也由同一规则覆盖。

伪代码/关键模板：

typedef struct ACExprNode {
    char data[10];
    struct ACExprNode *left;
    struct ACExprNode *right;
} ACExprNode;

void ac_print_infix(const ACExprNode *p, const ACExprNode *root) {
    if (p == NULL) return;
    int compound = p->left != NULL || p->right != NULL;
    int parenthesize = compound && p != root;
    if (parenthesize) fputc('(', stdout);
    ac_print_infix(p->left, root);
    fputs(p->data, stdout);
    ac_print_infix(p->right, root);
    if (parenthesize) fputc(')', stdout);
}

复杂度：遍历时间 O(n)，不计输出的递归栈 O(h)。

易错边界：data 是字符串，应使用 fputs/“%s”而不是字符格式；根无需最外层括号，叶结点也无需括号；空孩子必须先返回。

回源 · PDF 第 131 页 · b_131_3；PDF 第 131 页 · b_131_4；PDF 第 131 页 · b_131_7；PDF 第 131 页 · b_131_8；PDF 第 131 页 · b_131_10；PDF 第 131 页 · b_131_11；PDF 第 131 页 · b_131_12；PDF 第 131 页 · b_131_13；PDF 第 131 页 · b_131_14；PDF 第 132 页 · b_132_0；PDF 第 132 页 · b_132_1

2022 顺序存储 BST，怎样同时处理空洞、重复值和最小整数？¶

何时用：0 下标顺序树，-1 表示空结点，题目保证有效值为正整数，判断是否为 BST。

思路步骤：

下标越过 elem_num 或值为 -1 时，该空子树合法。
递归访问 2i+1。
当前值必须严格大于中序前驱；首次访问由 has_previous 区分。
更新前驱，再递归 2i+2。
每次主调用使用局部状态，避免全局 pre 污染下一棵树。

伪代码/关键模板：

int ac_seq_bst_rec(
    const ACSeqTree *tree, long long index, int *has_previous, int *previous
) {
    if (index >= tree->elem_num || tree->node[index] == -1) return 1;
    if (!ac_seq_bst_rec(tree, 2 * index + 1, has_previous, previous)) return 0;
    if (*has_previous && tree->node[index] <= *previous) return 0;
    *previous = tree->node[index];
    *has_previous = 1;
    return ac_seq_bst_rec(tree, 2 * index + 2, has_previous, previous);
}

int ac_seq_is_bst(const ACSeqTree *tree) {
    if (tree == NULL || tree->elem_num <= 0 || tree->elem_num > AC_MAXV) return 0;
    int has_previous = 0, previous = 0;
    return ac_seq_bst_rec(tree, 0, &has_previous, &previous);
}

复杂度：只访问数组表示的非空结点及必要空位，最坏 O(elem_num)，递归栈 O(h)。

易错边界：新版补充/校订：旧版比较写成 pre>current 会允许重复值；严格 BST 应在 current≤previous 时失败。局部 has_previous 也避免哨兵与跨调用污染。

回源 · PDF 第 132 页 · b_132_3；PDF 第 132 页 · b_132_4；PDF 第 132 页 · b_132_5；PDF 第 132 页 · b_132_6；PDF 第 132 页 · b_132_7；PDF 第 132 页 · b_132_14；PDF 第 132 页 · b_132_15；PDF 第 132 页 · b_132_16；PDF 第 132 页 · b_132_17；PDF 第 132 页 · b_132_18；PDF 第 132 页 · b_132_19；PDF 第 132 页 · b_132_20；PDF 第 132 页 · b_132_21；PDF 第 132 页 · b_132_22

第4章 树与二叉树算法