树与二叉树：手算与代码阅读

题目描述

本题为理论填空题。为了便于 HydroOJ 自动评测，请严格按照每题给出的作答格式填写。

1. 遍历序列推导

已知先序为：

ABDECFG

中序为：

DBEAFCG

写出后序遍历序列。

{{ input(1) }}

2. 由中序和后序重建二叉树

已知中序为：

BADCE

后序为：

BDECA

写出先序遍历序列，并说明二叉树结构。

请按下面格式填写：

先序序列；结构描述

{{ input(2) }}

3. 四种遍历

对于下面这棵二叉树，分别写出先序、中序、后序和层序遍历序列。

        A
      /   \
     B     C
    / \   / \
   D   E F   G

请按下面格式填写，四个序列之间使用英文逗号分隔：

先序,中序,后序,层序

{{ input(3) }}

4. DFS 代码阅读

阅读下面的 DFS 核心代码：

void dfs(int u, int f) {
    fa[u] = f;
    siz[u] = 1;
    h[u] = 1;

    bool leaf = true;

    for (int v : g[u]) {
        if (v == f) continue;

        leaf = false;
        dep[v] = dep[u] + 1;

        dfs(v, u);

        siz[u] += siz[v];
        h[u] = max(h[u], h[v] + 1);
    }

    if (leaf) leaf_cnt++;
}

说明为什么 siz[u] 与 h[u] 都必须在 dfs(v, u) 返回之后再更新。

请填写讲义中的核心结论：

{{ input(4) }}