历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing《PAT甲级辅导课》第5章树

作者：

姜萍Jumping , 2021-12-04 11:13:16 , 所有人可见 , 阅读 478

3

2

第5章树

1004. Counting Leaves

笔记

统计树每层叶子的个数，可用DFS或BFS
在DFS加入参数depth，可表示当前层号，但还需要全局变量记录树的层数
可用邻接表存储树

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, M = 210, ROOT = 1;
int n, m;
int h[N], e[M], ne[M], idx;
int cnt[N], max_depth;

void add(int u, int v) {
    e[idx] = v;
    ne[idx] = h[u];
    h[u] = idx++;
}

void dfs(int u, int depth) {
    if (h[u] == -1) {
        cnt[depth]++;       // 叶节点
        max_depth = max(max_depth, depth);
        return;
    }

    for (int p = h[u]; ~p; p = ne[p])
        dfs(e[p], depth + 1);
}

int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);

    int u, son, k;
    for (int i = 0; i < m; i++) {
        cin >> u >> k;
        while(k--) {
            cin >> son;
            add(u, son);
        }
    }

    dfs(ROOT, 0);

    cout << cnt[0];
    for (int i = 1; i <= max_depth; i++)
        cout << ' ' << cnt[i];
    cout << endl;

    return 0;
}

1020. Tree Traversals

笔记

根据中序遍历和后序遍历（或前序遍历）可唯一确定一棵二叉树
- 后序遍历序列 = $m_1$个数构成的左子树后序遍历序列 + $m_2$个数构成的左子树后序遍历序列 + 根节点
- 中序遍历序列 = $m_1$个数构成的左子树中序遍历序列 + 根节点 + $m_2$个数构成的左子树中序遍历序列
后序遍历最后一个位置是根节点，查找其在中序遍历的位置，可把中序遍历分成两段，左段是左子树的中序遍历，右段是右子树的中序遍历。根据左子树的中序遍历序列，可确定左子树的结点个数$m$，从而后序遍历前$m$个数构成的就是左子树的后序遍历序列，之后的数至倒数第二个就是右子树的后序遍历序列，借助递归则可继续做下去
构造完二叉树后可用BFS实现层序遍历
总结
- 左右孩子（哈希表）表示法存储树结构
- 后序+中序→构造二叉树
  - 递归实现
  - 用哈希表加快在中序序列查找结点位置
- BFS输出层序遍历
  - 手动实现队列，因为可以顺序输出

#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 35;
int n;
int inorder[N], postorder[N];
unordered_map<int, int> l, r, pos;

int build(int in_l, int in_r, int post_l, int post_r) {
    int root = postorder[post_r];   // 当前后序遍历段的根节点下标
    int k = pos[root];              // 根节点在中序遍历的位置（哈希表优化查找）
    if (in_l < k) {
        int m = (k - 1) - in_l + 1;     // 左子树结点个数
        l[root] = build(in_l, k - 1, post_l, post_l + (k - 1 - in_l));
    }
    if (k < in_r) {
        int m = in_r - (k + 1) + 1;     // 右子树结点个数
        r[root] = build(k + 1, in_r, post_l + (k - 1 - in_l) + 1, post_r - 1);
    }
    return root;
}

int q[N], hh, tt;

void bfs(int root) {
    q[++tt] = root;
    while(hh < tt) {
        int u = q[++hh];
        if (l.count(u)) q[++tt] = l[u];
        if (r.count(u)) q[++tt] = r[u];
    }

    cout << q[1];
    for (int i = 2; i <= n; i++) cout << ' ' << q[i];
    cout << endl;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> postorder[i];
    for (int i = 0; i < n; i++) {
        cin >> inorder[i];
        pos[inorder[i]] = i;        // 根据结点值查找其中序序列的位置
    }

    int root = build(0, n - 1, 0, n - 1);

    bfs(root);

    return 0;
}

1021. Deepest Root

笔记

可用并查集查找连通个数，每成功合并一次，则说明是树的一条边，如果给的所有边都能成功合并，则是一棵树，否则不能合并的边数就是连通数
可参照“树的中心”那题寻找各个点的最大深度，在本题中，各个边的权重都是1，不存在负数权值，能简化代码
总结
- 并查集判断是否是树，同时可求连通块个数
  - 合并次数 + 连通块个数 = n
    - 合并次数为n-1，则连通块个数为1，即为树
    - 否则n - 合并次数为连通块个数find(u) != find(v)时，合并
  - 根据求树的直径算法找到使树深度最大的根节点（树形DP）
    - 一个结点，向上可由最大向上长度，向下可由最大向下长度和次大向下长度。
    - 以结点u为根的树的深度 = max(u的最大向上长度，u的最大向下长度)
    - 最大向下长度和次大向下长度可在dfs中求出
    - 为了计算最大向上长度，需要保存最大向下长度所在的路径，假设v是u的子结点
      - u的最长向下路径经过v，v的最大向上长度 = max{u的最大向上长度, u的次大向下长度}
      - u的最长向下路径不经过v，v的最大向上长度 = max{u的最大向上长度, u的最大向下长度}
    - 在计算最大向下长度和最大向上长度时，都是往下遍历，不能往回走

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e4 + 10, M = 2 * N;

// 邻接表
int n;
int h[N], e[M], ne[M], idx;

void add(int u, int v) {
    e[idx] = v;
    ne[idx] = h[u];
    h[u] = idx++;
}

// 并查集
int parent[N];                           

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

// 树的中心
int d1[N], d2[N], p1[N], up[N];     

int dfs_down(int u, int father) {
    for (int p = h[u]; ~p; p = ne[p]) {
        int v = e[p];
        if (v == father) continue;      // 不往上走

        int d = 1 + dfs_down(v, u);
        if (d > d1[u]) {
            d2[u] = d1[u];
            d1[u] = d;
            p1[u] = v;
        } else if (d > d2[u]) 
            d2[u] = d;
    }

    return d1[u];
}

void dfs_up(int u, int father) {
    for (int p = h[u]; ~p; p = ne[p]) {
        int v = e[p];
        if (v == father) continue;      // 不往上走

        if (p1[u] == v) up[v] = 1 + max(up[u], d2[u]);      // u的最长路径经过v
        else up[v] = 1 + max(up[u], d1[u]);                 // u的最长路径不经过v

        dfs_up(v, u);
    }
}

int main() {
    cin >> n;
    int u, v;

    for (int i = 1; i <= n; i++) parent[i] = i;      // 初始化并查集

    memset(h, -1, sizeof h);            // 初始化邻接表

    int cnt = n;
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v;

        add(u, v);
        add(v, u);

        if (find(u) != find(v)) {
            parent[find(u)] = find(v);       // 合并
            cnt--;
        }
    }

    if (cnt > 1) printf("Error: %d components\n", cnt);
    else {
        // 找树的中心（树形DP）
        dfs_down(1, -1);
        dfs_up(1, -1);

        int max_depth = -1;
        for (int i = 1; i <= n; i++)
            max_depth = max(max_depth, max(up[i], d1[i]));

        for (int i = 1; i <= n; i++)
            if (max(up[i], d1[i]) == max_depth)
                cout << i << endl;
    }

    return 0;
}

1043. Is It a Binary Search Tree

笔记

把二叉搜索树的前序序列排序即可得到中序序列
若能根据前序序列和中序序列构造二叉树，则说明是一个二叉搜索树
可在构造二叉搜索树时，计算后序序列
总结
- 二叉搜索树的性质：左子树所有元素 < 根节点 <= 右子树所有元素
- 前序序列 = 根节点, 左子树结点（<）, 右子树结点（>=）
- 前序序列镜像 = 根节点, 右子树结点（>=）, 左子树结点（<）
- 因此只要左子树分界点与右子树分界点相差1，树就是二叉搜索树，同时还可在递归过程完成后序遍历
- 当队列保存的后序序列元素个数为n时，是二叉树，否则不是

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;

int n, cnt;
int pre[N], in[N], post[N];

bool build(int pre_l, int pre_r, int in_l, int in_r) {
    if (in_l > in_r) return true;

    int root = pre[pre_l];
    int k;
    for (k = in_l; k <= in_r; k++)
        if (in[k] == root)
            break;      // 从前往后找第1个root（重复元素的第1个）
    if (k > in_r) return false;

    bool res = true;
    if(!build(pre_l + 1, pre_l + 1 + (k - 1 - in_l), in_l, k - 1)) res = false;
    if(!build(pre_l + 1 + (k - 1 - in_l) + 1, pre_r, k + 1, in_r)) res = false;
    // res = res && build(pre_l + 1, pre_l + 1 + (k - 1 - in_l), in_l, k - 1);
    // res = res && build(pre_l + 1 + (k - 1 - in_l) + 1, pre_r, k + 1, in_r);
    post[cnt++] = root;

    return res;
}

bool build_r(int pre_l, int pre_r, int in_l, int in_r) {
    if (in_l > in_r) return true;

    int root = pre[pre_l];
    int k;
    for (k = in_r; k >= in_l; k--)
        if (in[k] == root)
            break;      // 从后往前找第1个root（重复元素的最后1个）
    if (k < in_l) return false;

    bool res = true;
    if(!build_r(pre_l + 1, pre_l + 1 + (k - 1 - in_l), in_l, k - 1)) res = false;
    if(!build_r(pre_l + 1 + (k - 1 - in_l) + 1, pre_r, k + 1, in_r)) res = false;
    // res = res && build(pre_l + 1, pre_l + 1 + (k - 1 - in_l), in_l, k - 1);
    // res = res && build(pre_l + 1 + (k - 1 - in_l) + 1, pre_r, k + 1, in_r);
    post[cnt++] = root;

    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> pre[i];
        in[i] = pre[i];
    }

    sort(in, in + n);

    if (build(0, n - 1, 0, n - 1)) {
        puts("YES");
        cout << post[0];
        for (int i = 1; i < n; i++) 
            cout << ' ' << post[i];
        cout << endl;
    } else {
        reverse(in, in + n);

        cnt = 0;
        if (build_r(0, n - 1, 0, n - 1)) {
            puts("YES");
            cout << post[0];
            for (int i = 1; i < n; i++) 
                cout << ' ' << post[i];
            cout << endl;
        } else puts("NO");
    }

    return 0;
}

1064. Complete Binary Search Tree

笔记

采用一维数组存储完全二叉树
根据中序遍历次序填入排好序的二叉搜索树元素构成的序列
按顺序输出一维数组即可得到层次遍历结果
总结
- 二叉搜索树的性质：中序序列 = 有序序列
- 二叉搜索树的性质：中序遍历次序（下标序列） = 0~n-1构成的二叉搜索树
- 按中序遍历次序在新数组填入中序序列，就能得到完成二叉搜索树。完全二叉搜索树可用一维数组表示，按顺序遍历就能得到层序遍历

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;

int n, a[N], b[N];
int cnt = 1;

void inorder(int u) {
    if (2 * u <= n) inorder(2 * u);
    b[u] = a[cnt++];
    if (2 * u + 1 <= n) inorder(2 * u + 1);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    sort(a + 1, a + n + 1);
    inorder(1);     // 按中序遍历填入

    cout << b[1];
    for (int i = 2; i <= n; i++) cout << ' ' << b[i];

    return 0;
}

1086. Tree Traversals Again

笔记

非递归后序遍历具有如下特点
- 首次一定是push，压入的元素一定是root
- 如果上一次操作是push，则当前结点是上一个结点的左孩子
- 如果上一次操作是pop，则当前结点是上一个结点的右孩子
记录所有结点的左右孩子后，即可用DFS从root开始输出其后序遍历次序
总结
- 非递归中序遍历特点
  - 首次一定是push，且是根节点
  - 假设当前操作是push(v)
    - 若上一个操作是push(u)，则v是u的左孩子
    - 若上一个操作是u = pop()，则v是u的右孩子
- 根据序列，采用左右孩子存储树结构，再用dfs实现后序遍历

#include <iostream>
#include <stack>
using namespace std;
const int N = 35;

int n, l[N], r[N];      // 左右孩子
string output;

void post_order(int u) {
    if (!u) return;     // 空节点

    post_order(l[u]);
    post_order(r[u]);
    output += to_string(u) + " ";
}

int main() {
    cin >> n;

    stack<int> s;
    string op;
    int root, x;
    int last = 0;   // 上一个结点
    int type = 0;   // 0表示push，1表示pop
    for (int i = 0; i < 2 * n; i++) {
        cin >> op;
        if (op == "Push") {
            cin >> x;
            if (!i) root = x;       // 首次压入是根节点
            else {
                if (type == 0) l[last] = x;     // 上次是push，当前结点是上个结点的左孩子
                else r[last] = x;       // 上次是pop，当前结点是上个结点的左孩子
            }

            s.push(x);      // 模拟栈压入
            last = x;
            type = 0;

        } else {
            // pop
            last = s.top();           // 模拟栈弹出
            s.pop();
            type = 1;
        }
    }

    post_order(root);

    cout << output.substr(0, output.size() - 1) << endl;       // 去掉末尾空格

    return 0;
}

1099. Build A Binary Search Tree

笔记

先用中序遍历把排好序的数填入，然后再用层序遍历输出
~p等价于p != -1
总结
- 二叉搜索树的性质：中序序列 = 有序序列
- 二叉搜索树的性质：中序遍历次序（下标序列） = 0~n-1构成的二叉搜索树
- 按中序遍历次序在新数组填入中序序列，就能得到二叉搜索树
- 用bfs输出层序遍历

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, ROOT = 0;

int n, l[N], r[N], w[N], a[N];

int cnt;
void inorder(int u) {
    if (u == -1) return;

    inorder(l[u]);
    a[u] = w[cnt++];        // 填数
    inorder(r[u]);
}

string res;
int q[N];
void bfs(int root) {
    int hh = 0, tt = 0;
    q[++tt] = root;

    while(hh < tt) {
        int x = q[++hh];
        if (l[x] != -1) q[++tt] = l[x];
        if (r[x] != -1) q[++tt] = r[x];
    }

    for (int i = 1; i <= n; i++) res += to_string(a[q[i]]) + " ";
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> l[i] >> r[i];
    for (int i = 0; i < n; i++) cin >> w[i];

    sort(w, w + n);

    inorder(ROOT);      // 中序遍历填数
    bfs(ROOT);

    cout << res.substr(0, res.size() - 1) << endl;

    return 0;
}

1102. Invert a Binary Tree

笔记

两种方法
- 方法1 不翻转
  - 实现层序遍历时，先加入右孩子，再加入左孩子
  - 实现中序遍历时，先遍历右子树，再遍历左子树
- 方法2 翻转
  - 采用后序遍历翻转，即访问时交换左右孩子
  - 正常实现层序遍历和中序遍历即可
总结
- 存储
  - 左右孩子法存储树结构
  - 父节点标记法找到根节点
- 算法
  - 层序：先右孩子，再左孩子
  - 中序：先右孩子，再根结点，最后左孩子

方法1 不翻转

#include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int n, l[N], r[N];
bool has_father[N];

string res_1;
int q[N];
void bfs(int root) {
    int hh = 0, tt = 0;
    q[++tt] = root;

    while(hh < tt) {
        int x = q[++hh];
        if (~r[x]) q[++tt] = r[x];
        if (~l[x]) q[++tt] = l[x];
    }

    for (int i = 1; i <= n; i++) res_1 += to_string(q[i]) + " ";
}

string res_2;
void inorder(int u) {
    if (u == -1) return;

    inorder(r[u]);
    res_2 += to_string(u) + " ";
    inorder(l[u]);
}

int main() {
    cin >> n;

    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    string ls, rs;
    for (int i = 0; i < n; i++) {
        cin >> ls >> rs;
        if (ls != "-") {
            l[i] = ls[0] - '0';
            has_father[l[i]] = true;
        }
        if (rs != "-") {
            r[i] = rs[0] - '0';
            has_father[r[i]] = true;
        }
    }

    int root = -1;
    for (int i = 0; i < n; i++)
        if (!has_father[i]) {
            root = i;
            break;
        }

    bfs(root);
    inorder(root);

    cout << res_1.substr(0, res_1.size() - 1) << endl;
    cout << res_2.substr(0, res_2.size() - 1) << endl;

    return 0;
}

方法2 翻转

#include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int n, l[N], r[N];
bool has_father[N];

void reverse(int u) {
    if (u == -1) return;

    reverse(l[u]);
    reverse(r[u]);
    swap(l[u], r[u]);
}

string res_1;
int q[N];
void bfs(int root) {
    int hh = 0, tt = 0;
    q[++tt] = root;

    while(hh < tt) {
        int x = q[++hh];
        if (~l[x]) q[++tt] = l[x];
        if (~r[x]) q[++tt] = r[x];
    }

    for (int i = 1; i <= n; i++) res_1 += to_string(q[i]) + " ";
}

string res_2;
void inorder(int u) {
    if (u == -1) return;

    inorder(l[u]);
    res_2 += to_string(u) + " ";
    inorder(r[u]);
}

int main() {
    cin >> n;

    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    string ls, rs;
    for (int i = 0; i < n; i++) {
        cin >> ls >> rs;
        if (ls != "-") {
            l[i] = ls[0] - '0';
            has_father[l[i]] = true;
        }
        if (rs != "-") {
            r[i] = rs[0] - '0';
            has_father[r[i]] = true;
        }
    }

    int root = -1;
    for (int i = 0; i < n; i++)
        if (!has_father[i]) {
            root = i;
            break;
        }

    reverse(root);
    bfs(root);
    inorder(root);

    cout << res_1.substr(0, res_1.size() - 1) << endl;
    cout << res_2.substr(0, res_2.size() - 1) << endl;

    return 0;
}

1110. Complete Binary Tree

笔记

模拟构造完全二叉树，如果所有结点的最大编号刚好为$n$（从1开始编号），则是一个完全二叉树，否则不是
总结
- 用dfs模拟完全二叉树的填充，记录填充最大位置及相应的结点，如果最大位置恰好为n，则是完全二叉树

#include <iostream>
#include <cstring>
using namespace std;
const int N = 25;

int n, l[N], r[N];
bool has_father[N];
int max_u = -1, max_k = -1;

void dfs(int u, int k) {
    if (u == -1) return;

    if (k > max_k) {
        max_u = u;
        max_k = k;
    }

    dfs(l[u], 2 * k);
    dfs(r[u], 2 * k + 1);
}

int main () {
    cin >> n;

    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    string ls, rs;
    for (int i = 0; i < n; i++) {
        cin >> ls >> rs;
        if (ls != "-") {
            l[i] = stoi(ls);
            has_father[l[i]] = true;
        }
        if (rs != "-") {
            r[i] = stoi(rs);
            has_father[r[i]] = true;
        }
    }

    int root = 0;
    while(has_father[root]) root++;

    dfs(root, 1);       // 从1开始填完全二叉树

    if (max_k == n) printf("YES %d\n", max_u);
    else printf("NO %d\n", root);

    return 0;
}

1115. Counting Nodes in a BST

笔记

构造二叉搜索树，注意从1开始编号，insert(int& u, int x)可自动更新左右子树指针
用DFS遍历所有结点，计算各层结点数，同时还要保存最大层数
总结
- 构造二叉搜索树，用左右孩子存储树结构
- 用dfs求各层结点个数，以及最大深度

#include <iostream>
using namespace std;
const int N = 1010;

int n, l[N], r[N], v[N], idx;

int cnt[N], max_depth;

void insert(int &u, int x) {
    // 从结点u开始插入x
    if (!u) {
        // 首次插入
        u = ++idx;       // 计算可用结点位置（数组下标表示），并保存（引用可修改变量）
        v[u] = x;        // 保存该结点
    } else if (x <= v[u]) insert(l[u], x);  // 若插入成功，则会修改l[u]的值，指向新结点地址
    else insert(r[u], x);                   // 若插入成功，则会修改r[u]的值，指向新结点地址
}

void dfs(int u, int depth) {
    if (!u) return;
    cnt[depth]++;
    max_depth = max(max_depth, depth);

    dfs(l[u], depth + 1);
    dfs(r[u], depth + 1);
}

int main() {
    cin >> n;

    int x;
    int root = 0;       // 0表示首次插入
    for (int i = 0; i < n; i++) {
        cin >> x;
        insert(root, x);        // 自动更新当前root位置
    }

    dfs(root, 0);

    int n1 = cnt[max_depth], n2 = cnt[max_depth - 1];
    printf("%d + %d = %d\n", n1, n2, n1 + n2);

    return 0;
}

1119. Pre- and Post-order Traversals

笔记

用DFS搜索，如果找到一种情况，则继续搜索，如果找到一种以上的情况，则可停止
可根据前序遍历序列划分左右子树，即根节点 + 左子树区间 + 右子树区间，可在左右边界穷举所有情况

#include <iostream>
using namespace std;
const int N = 40;

int pre[N], post[N], in[N];

// 返回合法方案数
int dfs(int pre_l, int pre_r, int post_l, int post_r, string& res) {
    if (pre_l > pre_r) return 1;                    // 合法情况
    if (pre[pre_l] != post[post_r]) return 0;       // 非法情况

    int cnt = 0;
    for (int k = pre_l; k <= pre_r; k++) {
        string l_res, r_res;
        int l_cnt = dfs(pre_l + 1, k, post_l, post_l + k - pre_l - 1, l_res);
        int r_cnt = dfs(k + 1, pre_r, post_l + k - pre_l - 1 + 1, post_r - 1, r_res);

        if (l_cnt && r_cnt) {
            cnt += l_cnt * r_cnt;
            res = l_res + to_string(pre[pre_l]) + " " + r_res;
            if (cnt > 1) break;
        }
    }
    return cnt;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> pre[i];
    for (int i = 0; i < n; i++) cin >> post[i];

    string res;
    int cnt = dfs(0, n - 1, 0, n - 1, res);

    if (cnt > 1) puts("No");
    else puts("Yes");

    cout << res.substr(0, res.size() - 1) << endl;

    return 0;
}

1127. ZigZagging on a Tree

笔记

重建二叉树，再层序遍历
可在BFS中确定二叉树每一层结点的范围，内嵌一层while即可做到

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 35;

unordered_map<int, int> l, r, pos;       // 左右孩子
int n, in[N], post[N];

int build(int in_l, int in_r, int post_l, int post_r) {
    int root = post[post_r];
    int k = pos[root];        // 查找root在中序遍历的下标
    if (in_l < k) l[root] = build(in_l, k - 1, post_l, post_l + k - 1 - in_l);
    if (k < in_r) r[root] = build(k + 1, in_r, post_l + k - 1 - in_l + 1, post_r - 1);

    return root;
}

string res;
int q[N];
void bfs(int root) {
    int hh = 0, tt = 0;
    q[0] = root;

    bool flag = true;
    while(hh <= tt) {
        int head = hh, tail = tt;
        while(hh <= tail) {
            int u = q[hh++];
            if (l.count(u)) q[++tt] = l[u];
            if (r.count(u)) q[++tt] = r[u];
        }

        if (flag) reverse(q + head, q + tail + 1);
        flag = !flag;
    }

    for (int i = 0; i < n; i++)
        res += to_string(q[i]) + ' ';
    res.pop_back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> in[i];
        pos[in[i]] = i;       // 哈希表，加快查找下标
    }
    for (int i = 0; i < n; i++) cin >> post[i];

    int root = build(0, n - 1, 0, n - 1);
    bfs(root);

    cout << res << endl;

    return 0;
}

1138. Postorder Traversal

笔记

DFS后序构造二叉树，但不保存左右孩子位置
由于只需记录后序遍历首次遍历的结点，故只需判段用来保存的变量是否变更即可

#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 5e4 + 10;

unordered_map<int, int> pos;
int n, in[N], pre[N];
int post;       // 后序遍历第1个结点

void build(int in_l, int in_r, int pre_l, int pre_r) {
    int root = pre[pre_l];
    int k = pos[root];

    if (in_l < k) build(in_l, k - 1, pre_l + 1, pre_l + 1 + k - 1 - in_l);
    if (k < in_r) build(k + 1, in_r, pre_l + 1 + k - 1 - in_l + 1, pre_r);

    if (!post) post = root;     // 后序遍历第1个结点
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) cin >> pre[i];
    for (int i = 0; i < n; i++) {
        cin >> in[i];
        pos[in[i]] = i;
    }

    build(0, n - 1, 0, n - 1);

    cout << post << endl;

    return 0;
}

1066. Root of AVL Tree

笔记

插入一个新结点可分为三步：① 插入结点； ② 调整位置； ③ 更新高度
- 插入结点的过程与查找二叉树一样
- 调整位置共有4类情况（LL、LR、RR、RL），可通过计算左右孩子的高度差判断。每种情况可通过两个基本步骤左旋和右旋的组合来解决。在把孩子变成根节点前，需要把孩子多余的部分移到原来的根节点上
- 更新高度需要从下往上更新
性质：左旋和右旋只会改变平衡二叉树的位置和高度，但中序遍历次序不变
代码实现需要修改根节点指向，因此需要用引用型参数&

#include <iostream>
#include <cstring>
using namespace std;
const int N = 30;
int l[N], r[N], w[N], idx;      // 左右儿子法实现平衡二叉树
int h[N];                       // 树高

int get_balance(int u) {
    return h[l[u]] - h[r[u]];           // 平衡度
}

void update(int u) {
    h[u] = max(h[l[u]], h[r[u]]) + 1;       // 更新结点高度
}

void R(int& u) {
    int p = l[u];
    l[u] = r[p];            // 不然左孩子的右孩子不为空，放不了根节点
    r[p] = u;
    update(u);              // 从下往上更新
    update(p);
    u = p;                  // 更新根节点
}

void L(int& u) {
    int p = r[u];
    r[u] = l[p];            // 不然左孩子的右孩子不为空，放不了根节点
    l[p] = u;
    update(u);              // 从下往上更新
    update(p);
    u = p;                  // 更新根节点
}

void insert(int &u, int v) {
    if (!u) {
        u = ++idx;
        w[u] = v;
    } else if (v < w[u]) {
        // 先插入，再调整，最后更新
        insert(l[u], v);        
        if (get_balance(u) == 2) {
            if (get_balance(l[u]) == 1) R(u);
            else {
                L(l[u]);
                R(u);
            }
        }
    } else {
        insert(r[u], v);
        if (get_balance(u) == -2) {
            if (get_balance(r[u]) == -1) L(u);
            else {
                R(r[u]);
                L(u);
            }
        }
    }

    update(u);
}

int main() {
    int n, v;
    cin >> n;

    int root = 0;       // 从第0个位置开始插入
    for (int i = 0; i < n; i++) {
        cin >> v;
        insert(root, v);        // 插入到平衡二叉树中
    }

    cout << w[root] << endl;

    return 0;   
}

1123. Is It a Complete AVL Tree.

笔记

首先构造平衡二叉树，然后采用BFS边输出层序遍历，边判断是否是完全二叉树，如果插入结点的位置超过$n$，则认为不是完全二叉树

#include <iostream>
using namespace std;
const int N = 25;
int n, l[N], r[N], w[N], h[N], idx;

int get_balance(int u) {
    return h[l[u]] - h[r[u]];
}

void update(int u) {
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}

void R(int& u) {
    int p = l[u];
    l[u] = r[p];
    r[p] = u;
    update(u);
    update(p);
    u = p;
}

void L(int& u) {
    int p = r[u];
    r[u] = l[p];
    l[p] = u;
    update(u);
    update(p);
    u = p;
}

void insert(int& u, int x) {
    if (!u) {
        u = ++idx;
        w[u] = x;
    } else if (x < w[u]) {
        insert(l[u], x);
        if (get_balance(u) == 2) {
            if (get_balance(l[u]) == 1) R(u);
            else {
                L(l[u]);
                R(u);
            }
        }
    } else {
        insert(r[u], x);
        if (get_balance(u) == -2) {
            if (get_balance(r[u]) == -1) L(u);
            else {
                R(r[u]);
                L(u);
            }
        }
    }

    update(u);
}

int q[N], pos[N];
void bfs(int root) {
    int hh = 0, tt = -1;
    q[++tt] = root;

    pos[root] = 1;      // 模拟完全二叉树
    bool flag = true;        // 是否是二叉树
    while(hh <= tt) {
        int u = q[hh++];
        if (pos[u] > n) flag = false;       // 超出完全二叉树的保存范围
        if (l[u]) {
            q[++tt] = l[u];
            pos[l[u]] = 2 * pos[u];
        }
        if (r[u]) {
            q[++tt] = r[u];
            pos[r[u]] = 2 * pos[u] + 1;
        }
    }

    string res;
    for (int i = 0; i < n; i++) res += to_string(w[q[i]]) + ' ';
    res.pop_back();
    cout << res << endl;

    if (flag) puts("YES");
    else puts("NO");
}

int main() {
    cin >> n;

    int x, root = 0;
    for (int i = 0; i < n; i++) {
        cin >> x;
        insert(root, x);
    }

    bfs(root);
}

1135. Is It A Red-Black Tree

笔记

实际上只需要检查三个条件
- 根节点为黑（在建树后检查）
- 红结点的孩子都为黑结点（建树中检查）
- 根节点到叶节点的路径具有相同的黑结点个数（建树中检查）
建树依据
- 红黑树是一个平衡二叉树，其中序遍历序列就是所有结点的升序排序序列，
- 把前序遍历序列排序后就能得到中序序列，从而有可能根据前序和中序序列构造唯一的二叉树
注意
- 红色是负权值，在排序获取中序遍历序列时需要去掉符号再排序

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 35;
int n, pre[N], in[N];
unordered_map<int, int> pos;
bool flag;

int build(int pre_l, int pre_r, int in_l, int in_r, int& sum) {
    int root = pre[pre_l];
    int k = pos[abs(root)];
    if (k < in_l || k > in_r) {
        flag = false;
        return 0;
    }

    int left = 0, right = 0, ls = 0, rs = 0;
    if (k > in_l) left = build(pre_l + 1, pre_l + 1 + k - 1 - in_l, in_l, k - 1, ls);
    if (k < in_r) right = build(pre_l + 1 + k - 1 - in_l + 1, pre_r, k + 1, in_r, rs);

    if (ls != rs) flag = false;       // 黑结点个数不等

    sum = ls;       // 更新sum的值

    if (root < 0) {
        if (left < 0 || right < 0) flag = false; // 红色根节点存在黑结点孩子
    } else sum++;       // 根节点是黑结点，到叶节点的黑结点个数+1

    return root;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> n;

        for (int i = 0; i < n; i++) {
            cin >> pre[i];
            in[i] = abs(pre[i]);
        }

        sort(in, in + n);
        // for (int i = 0; i < n; i++) cout << pre[i] << endl;

        for (int i = 0; i < n; i++) pos[in[i]] = i;

        int sum = 0;
        flag = true;
        int root = build(0, n - 1, 0, n - 1, sum);
        if (root < 0) flag = false;
        if (flag) puts("Yes");
        else puts("No");

        pos.clear();
    }

    return 0;
}

1053. Path of Equal Weight

笔记

可采用邻接矩阵存储多叉树
可用额外的叶节点数组标记结点是否是叶节点，提高算法效率
采用DFS即可找到所有到叶节点的路径

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 110, ROOT = 0;
int n, m, target;        // 结点个数，非叶子结点个数，目标权值
int w[N];           // 权重
bool g[N][N];       // 邻接矩阵存储多叉树
bool is_leaf[N];    // 是否是叶节点

vector<vector<int>> res;

void dfs(int u, int s, vector<int>& path) {
    if (is_leaf[u] && s == target) res.push_back(path);
    else {
        for (int v = 0; v < n; v++)
            if (g[u][v]) {
                path.push_back(w[v]);
                dfs(v, s + w[v], path);
                path.pop_back();
            }
    }
}

int main() {

    cin >> n >> m >> target;
    for (int i = 0; i < n; i++) cin >> w[i];
    while(m--) {
        int u, k, v;
        cin >> u >> k;
        is_leaf[u] = true;       // 先标记非叶节点，等会儿再处理
        while(k--) {
            cin >> v;
            g[u][v] = true;     // 构造邻接矩阵
        }
    }

    for (int i = 0; i < n; i++) is_leaf[i] = !is_leaf[i];  // 变成正确含义

    vector<int> path{w[ROOT]};
    dfs(ROOT, w[ROOT], path);

    sort(res.begin(), res.end(), greater<vector<int>>());
    for (auto elem : res) {
        string line;
        for (int item : elem) line += to_string(item) + ' ';
        line.pop_back();
        cout << line << endl;
    }

    return 0;   
}

1094. The Largest Generation

笔记

用BFS找到结点数最多的层
BFS不仅能用queue实现，还可以用vector实现

#include <iostream>
#include <vector>
using namespace std;
const int N = 110, ROOT = 1;
int n, m;           // 结点个数，非叶子结点个数
bool g[N][N];       // 邻接矩阵

vector<int> level[N];

void bfs(int root) {
    int l = 1;
    level[1].push_back(root);

    while(level[l].size()) {
        for (auto u : level[l])
            for (int v = 1; v <= n; v++)
                if (g[u][v]) level[l + 1].push_back(v);
        l++;
    }

    int max_l = 0, max_nodes = 0;
    for (int i = 1; i < l; i++)
        if (max_nodes < level[i].size()) {
            max_l = i;
            max_nodes = level[i].size();
        }

    cout << max_nodes << ' ' << max_l << endl;
}

int main() {

    cin >> n >> m;
    while(m--) {
        int u, k, v;
        cin >> u >> k;
        while(k--) {
            cin >> v;
            g[u][v] = true;
        }
    }

    bfs(ROOT);

    return 0;
}

1079. Total Sales of Supply Chain

笔记

采用树形DP把$O(n^2)$空间复杂度降为$O(n)$，因为只需存储父节点，不存储整个树结构
采用记忆化搜索把树形DP$O(n^2)$时间复杂度降为$O(n)$，因为减少了重复计算
用$n$维数组保存每个结点的销售量，如果是非零售商，则销售量为$0$，可以据此区分叶节点和非叶节点

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int n;
int p[N];       // 父节点
int f[N];       // 树形DP（记忆化搜索），存储树的深度
int cnt[N];     // 销售个数（非零售商是0）

// 记忆化搜索优化树形DP
int dfs(int u) {
    if (f[u] != -1) return f[u];

    if (p[u] == -1) {
        f[u] = 0;       // 根节点的深度为0
        return f[u];
    }

    f[u] = dfs(p[u]) + 1;
    return f[u];
}

int main() {
    double price, rate;
    cin >> n >> price >> rate;

    int k, child;
    memset(p, -1, sizeof p);        
    for (int i = 0; i < n; i++) {
        cin >> k;

        if (k > 0) {
            // 读入子结点
            for (int j = 0; j < k; j++) {
                cin >> child;
                p[child] = i;       // 标记父节点
            } 
        } else 
            cin >> cnt[i];      // 读入零售商的销售数量
    }

    memset(f, -1, sizeof f);        // 树的深度(DP),-1表示未计算过

    double res = 0;
    for (int i = 0; i < n; i++)
        if (cnt[i])             // 非0说明是零售商
            res += price * pow(1 + rate / 100, dfs(i)) * cnt[i];

    printf("%.1lf\n", res);

    return 0;   
}

1090. Highest Price in Supply Chain

笔记

和《Total Sales of Supply Chain》类似，树形DP+记忆化搜索

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int n, p[N], f[N];

int dfs(int u) {
    if (f[u] != -1) return f[u];
    else if (p[u] == -1) return f[u] = 0;
    else return f[u] = dfs(p[u]) + 1;
}


int main() {
    double price, rate;
    cin >> n >> price >> rate;
    for (int i = 0; i < n; i++)
        cin >> p[i];

    memset(f, -1, sizeof f);

    int max_d = -1, cnt = 1;
    for (int i = 0; i < n; i++)
        if (dfs(i) > max_d) {
            max_d = dfs(i);
            cnt = 1;        // 重置
        } else if (dfs(i) == max_d) cnt++;

    printf("%.2lf %d\n", price * pow(1 + rate / 100, max_d), cnt);

    return 0;
}

1106. Lowest Price in Supply Chain

笔记

本题与《Highest Price in Supply Chain》类似，也是采用树形DP+记忆化搜索优化时间空间复杂度，但由于路径短的不一定是叶结点，因此需要额外的变量保存叶节点信息

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;

int n, p[N], f[N];
bool is_leaf[N];

int dfs(int u) {
    if (f[u] != -1) return f[u];
    if (p[u] == -1) return f[u] = 0;
    return f[u] = dfs(p[u]) + 1;
}

int main() {
    double price, rate;
    cin >> n >> price >> rate;

    int k, child;
    memset(p, -1, sizeof p);
    for (int i = 0; i < n; i++) {
        cin >> k;
        if (k > 0) {
            while(k--) {
                cin >> child;
                p[child] = i;
            }
        } else is_leaf[i] = true;       // 标记叶节点
    }

    memset(f, -1, sizeof f);

    int min_d = 2e9, cnt = 1;
    for (int i = 0; i < n; i++)
        if (is_leaf[i]) {
            if (dfs(i) < min_d) {
                min_d = dfs(i);
                cnt = 1;
            } else if (dfs(i) == min_d) cnt++; 
        }

    printf("%.4lf %d\n", price * pow(1 + rate / 100, min_d), cnt);

    return 0;
}

1155. Heap Paths

笔记

判断是否是堆以及是什么堆的思路
- 用两个布尔变量lt和gt标记父节点和子结点的大小关系，可在DFS输出路径的时候更新变量
- 如果lt和gt同时为true，则不是堆
- 如果仅有lt为true，则是小根堆
- 如果仅有gt为true，则是大根堆
注意先输出右子树，再输出左子树

#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int n, a[N];
vector<int> path;
bool lt, gt;        // 用于判断是否是堆以及是大根堆还是小根堆

void dfs(int u) {
    path.push_back(a[u]);
    if (2 * u > n) {
        // 叶节点，输出路径
        cout << path[0];
        for (int i = 1; i < path.size(); i++) {
            if (path[i - 1] < path[i]) lt = true;
            else gt = true;
            cout << ' ' << path[i];
        }
        cout << endl;
    }

    if (2 * u + 1 <= n) dfs(2 * u + 1);
    if (2 * u <= n) dfs(2 * u);

    path.pop_back();
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    dfs(1);

    if (lt && gt) puts("Not Heap");
    else if (lt) puts("Min Heap");
    else puts("Max Heap");

    return 0;
}

1130. Infix Expression

笔记

中序遍历即可
注意用一个布尔数组st标记非根节点，这样才能找到根节点
还需要一个布尔数组is_leaf标记叶节点，如果不是叶节点则在两侧输出括号

#include <iostream>
using namespace std;
const int N = 25;

int n;
string w[N];
int l[N], r[N];
bool st[N];             // 标记非根节点，用来找根节点
bool is_leaf[N];        // 标记叶节点

string inorder(int u) {
    string left, right;
    if (l[u] != -1) {
        left = inorder(l[u]);
        if (!is_leaf[l[u]]) left = '(' + left + ')';
    }
    if (r[u] != -1) {
        right = inorder(r[u]);
        if (!is_leaf[r[u]]) right = '(' + right + ')';
    }
    return left + w[u] + right;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> l[i] >> r[i];
        st[l[i]] = st[r[i]] = true;
        if (l[i] == -1 && r[i] == -1) is_leaf[i] = true;
    }

    int root = 1;
    while(st[root]) root++;

    cout << inorder(root) << endl;

    return 0;
}

1143. Lowest Common Ancestor

笔记

把前序序列排序即可得到二叉搜索树的中序序列，根据前序和中序序列重建二叉搜索树（父节点表示法），同时记录各个结点的深度
对于每组查询，首先把查询两个结点是否存在，如果都存在，则每次把较深的结点向上移动，直到二者相等
比较移动前后的结果即可判断二者是LCA还是祖先关系

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 1e4 + 10;
int n, seq[N], pre[N], in[N], depth[N];
int p[N];
unordered_map<int, int> pos;

int build(int pre_l, int pre_r, int in_l, int in_r, int d) {
    int root = pre[pre_l];  // 根节点在哈希表的下标
    int k = root;           // root同时也是中序遍历的下标

    depth[k] = d;

    if (in_l < k) {
        int lchild = build(pre_l + 1, pre_l + 1 + k - 1 - in_l, in_l, k - 1, d + 1);
        p[lchild] = root;
    }
    if (k < in_r) {
        int rchild = build(pre_l + 1 + k - 1 - in_l + 1, pre_r, k + 1, in_r, d + 1);
        p[rchild] = root;
    }

    return root;
}

int main() {
    int q;
    cin >> q >> n;
    for (int i = 0; i < n; i++) {
        cin >> pre[i];
        seq[i] = pre[i];
    }
    sort(seq, seq + n);             

    for (int i = 0; i < n; i++) {
        pos[seq[i]] = i;        // 构造哈希表
        in[i] = i;              // 构造中序序列（保存的是元素在哈希表的位置）
    }

    for (int i = 0; i < n; i++)
        pre[i] = pos[pre[i]];   // 更新前序序列元素，替换成哈希表元素下标

    build(0, n - 1, 0, n - 1, 0);

    int u, v;
    while(q--) {
        cin >> u >> v;

        if (pos.count(u) == 0 && pos.count(v) == 0)
            printf("ERROR: %d and %d are not found.\n", u, v);
        else if (pos.count(u) == 0)
            printf("ERROR: %d is not found.\n", u);
        else if (pos.count(v) == 0)
            printf("ERROR: %d is not found.\n", v);
        else {
           int a = pos[u], b = pos[v];      // 哈希表位置
           int x = a, y = b;                // 备份位置

            while(a != b)
                if (depth[a] > depth[b]) a = p[a];
                else b = p[b];

            if (a != x && b != y) 
                printf("LCA of %d and %d is %d.\n", u, v, seq[a]);
            else if (a == x) 
                printf("%d is an ancestor of %d.\n", seq[x], seq[y]);
            else
                printf("%d is an ancestor of %d.\n", seq[y], seq[x]);
        }

    }

    return 0;
}

1151. LCA in a Binary Tree

笔记

和《Lowest Common Ancestor》类似，只是上题没有直接给出中序序列，而是通过“二叉查找树”这个条件间接给了。而本题直接给了中序序列。
思路与上题一致，构建二叉查找树后，再用爬山法找LCA

#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 10010;

int n, p[N];
int seq[N], in[N], pre[N], depth[N];
unordered_map<int, int> pos;

int build(int pre_l, int pre_r, int in_l, int in_r, int d) {
    int root = pre[pre_l];
    int k = root;

    depth[root] = d;

    if (in_l < k) {
        int lchild = build(pre_l + 1, pre_l + 1 + k - 1 - in_l, in_l, k - 1, d + 1);
        p[lchild] = root;
    }
    if (k < in_r) {
        int rchild = build(pre_l + 1 + k - 1 - in_l + 1, pre_r, k + 1, in_r, d + 1);
        p[rchild] = root;
    }

    return root;
}

int main() {
    int q;
    cin >> q >> n;
    for (int i = 0; i < n; i++) {
        cin >> seq[i];
        pos[seq[i]] = i;                 // 构造哈希表
        in[i] = i;
    }

    for (int i = 0; i < n; i++) {
        cin >> pre[i];  
        pre[i] = pos[pre[i]];           // 更新为哈希表的下标
    }

    build(0, n - 1, 0, n - 1, 0);       // 构建二叉搜索树

    int u, v;
    while(q--) {
        cin >> u >> v;

        if (pos.count(u) == 0 && pos.count(v) == 0)
            printf("ERROR: %d and %d are not found.\n", u, v);
        else if (pos.count(u) == 0)
            printf("ERROR: %d is not found.\n", u);
        else if (pos.count(v) == 0)
            printf("ERROR: %d is not found.\n", v);
        else {
            int a = pos[u], b = pos[v];
            int x = a, y = b;

            while(a != b)
                if (depth[a] > depth[b]) a = p[a];
                else b = p[b];

            if (a != x && b != y)
                printf("LCA of %d and %d is %d.\n", seq[x], seq[y], seq[a]);
            else if (a == x)
                printf("%d is an ancestor of %d.\n", seq[x], seq[y]);
            else
                printf("%d is an ancestor of %d.\n", seq[y], seq[x]);
        }
    }

    return 0;
}

0 评论

App 内打开

AcWing《PAT甲级辅导课》 第5章 树

第5章 树

1004. Counting Leaves

1020. Tree Traversals

1021. Deepest Root

1043. Is It a Binary Search Tree

1064. Complete Binary Search Tree

1086. Tree Traversals Again

1099. Build A Binary Search Tree

1102. Invert a Binary Tree

1110. Complete Binary Tree

1115. Counting Nodes in a BST

1119. Pre- and Post-order Traversals

1127. ZigZagging on a Tree

1138. Postorder Traversal

1066. Root of AVL Tree

1123. Is It a Complete AVL Tree.

1135. Is It A Red-Black Tree

1053. Path of Equal Weight

1094. The Largest Generation

1079. Total Sales of Supply Chain

1090. Highest Price in Supply Chain

1106. Lowest Price in Supply Chain

1155. Heap Paths

1130. Infix Expression

1143. Lowest Common Ancestor

1151. LCA in a Binary Tree

0 评论

AcWing《PAT甲级辅导课》第5章树

第5章树