PAT甲级刷题记录-(AcWing)-(Day05树 8题)

PAT甲级刷题记录-(AcWing)-(Day05树 8题)

课程来源AcWing
其中AcWing中的题目为翻译好的中文题目

今日刷题列表

• 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

1004 Counting Leaves

AcWing链接
PAT链接

英语单词

• family hierarchy 家庭层次结构
• pedigree tree 谱系树
• For the sake of simplicity 为了简单起见
• sake 好处,目的
• for every seniority level 对于每一个级别

解析
使用DFS来遍历二叉树,基本操作可以看代码模板
这里在DFS的过程中记录当前的深度,并且记录当前层叶节点的个数

#include 
#include 

const int N = 110;
using namespace std;
int n, m;
int h[N], e[N], ne[N], idx = 0;
int max_depth, cnt[N];

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

void dfs(int u, int depth) {
    if (h[u] == -1) {
        // 是叶子节点
        max_depth = max(depth, max_depth);
        cnt[depth] += 1;
        return;
    }
    for (int i = h[u]; i != -1; i = ne[i]) {
        dfs(e[i], depth + 1);
    }
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    while (m--) {
        int id, k;
        cin >> id >> k;
        for (int i = 0; i < k; ++i) {
            int son;
            cin >> son;
            add(id, son);
        }
    }
    dfs(1, 0);
    cout << cnt[0];
    for (int i = 1; i <= max_depth; ++i) {
        cout << " " << cnt[i];
    }
}

1020 Tree Traversals

AcWing链接
PAT链接

英语单词

解析
给了前序和中序, 求层次遍历
先构建,再遍历即可

注意点

• 使用unordered_map l, r, pos;来存储节点的左孩子,右孩子,中序遍历中的位置

#include 
#include 
#include 

const int N = 40;
using namespace std;
int postorder[N], inorder[N];
unordered_map l, r, pos;
int n;
int q[N];

int build(int pl, int pr, int il, int ir) {
    int root = postorder[pr];
    int k = pos[root]; // k表示root在中序遍历中的索引
    if (il < k) l[root] = build(pl, pl + (k - 1 - il), il, k - 1);
    if (k < ir) r[root] = build(pl + (k - 1 - il) + 1, pr - 1, k + 1, ir);
    return root;
}

void bfs(int root) {
    q[0] = root;
    int head = 0, tail = 0;
    while (head <= tail) {
        int t = q[head++];
        if (l.count(t)) q[++tail] = l[t];
        if (r.count(t)) q[++tail] = r[t];

    }
    cout << q[0];
    for (int i = 1; i < n; ++i) {
        cout << " " << q[i];
    }
}

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

AcWing链接
PAT链接

英语单词

• acyclic 非循环的

解析

注意点

• 用到了并查集的知识
• 用到了使用dfs求树的深度

#include 
#include 
#include 

using namespace std;
const int N = 10010;
int h[N], e[2 * N], ne[2 * N], idx = 0;
int p[N];

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

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

int dfs(int x, int parent) {
    int depth = 0;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int node = e[i];
        if (node == parent) continue;
        depth = max(depth, dfs(node, x) + 1);
    }
    return depth;
}

int main() {
    int n;
    cin >> n;
    memset(h, -1, sizeof(h));
    for (int i = 0; i < n; ++i) {
        p[i] = i;
    }
    int k = n;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b)) {
            k--;
            p[find(a)] = find(b);
        }
        add(a, b);
        add(b, a);
    }
    if (k > 1)cout << "Error: " << k << " components";
    else {
        vector nodes;
        int max_depth = -1;
        for (int i = 1; i <= n; ++i) {
            int depth = dfs(i, -1);
            if (depth > max_depth) {
                max_depth = depth;
                nodes.clear();
                nodes.push_back(i);
            } else if (depth == max_depth)
                nodes.push_back(i);
        }
        for (int i = 0; i < nodes.size(); ++i) {
            cout  << nodes[i] << endl;
        }
    }
    return 0;
}

1043 Is It a Binary Search Tree

AcWing链接
PAT链接

英语单词

• recursively 递归的

解析
给出树的前序序列

• 而二叉搜索树的中序遍历本身就是有序的(右子树大于等于根节点,所以在找中序列表中索引的时候从左往右找第一个出现的值即可)
• 二叉搜索时的镜像树,它的中序遍历相当于从大到小的一个排序(此时左子树大于等于右子树,所以在找中序遍历的时候要从右往左找第一个出现的值)

#include 
#include 
#include 

const int N = 1010;

using namespace std;
int pre_order[N], post_order[N], idx = 0;
int mid_order[N];//中序
bool build(int pl, int pr, int ml, int mr, int is_mirror) {
    if (pl > pr) return true;
    int root = pre_order[pl];
    int k;
    if (is_mirror == 0) {
        for (k = ml; k <= mr; ++k) {
            if (mid_order[k] == root) // 从左往右找第一个和root相等的
                break;
        }
        if (k == mr + 1) return false;
    } else {
        for (k = mr; k >= ml; k--) {
            if (mid_order[k] == root)
                break;
        }
        if (k == ml - 1) return false;
    }
    // k是当前root节点在中序遍历中的位置
    bool res = true;
    // 左根右
    if (!build(pl + 1, pl + 1 + (k - 1 - ml), ml, k - 1, is_mirror)) res = false;
    if (!build(pl + 2 + (k - 1 - ml), pr, k + 1, mr, is_mirror)) res = false;
    post_order[idx++] = root;
    return res;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> pre_order[i];
        mid_order[i] = pre_order[i];
    }
    sort(mid_order, mid_order + n);
    if (build(0, n - 1, 0, n - 1, 0)) {
        cout << "YES" << endl;
        cout << post_order[0];
        for (int i = 1; i < n; ++i) {
            cout << " " << post_order[i];
        }
    } else {
        reverse(mid_order, mid_order + n);
        idx = 0;
        if (build(0, n - 1, 0, n - 1, 1)) {
            cout << "YES" << endl;
            cout << post_order[0];
            for (int i = 1; i < n; ++i) {
                cout << " " << post_order[i];
            }
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}
//7
//8 6 5 7 10 8 11

1064 Complete Binary Search Tree

AcWing链接
PAT链接

英语单词

解析
先将输入的节点排序,得到完全二叉搜索树的中序遍历结果mid_order
再走一遍中序遍历,将排好序的值按mid_order的顺序插入lever_order对应的位置中
最后从头到尾遍历一遍level_order就是层次遍历

注意点
完全二叉树的遍历要保证二叉树的存储是从1开始的,所以这边dfs(1,k)节点从1开始存.

#include 
#include 

const int N = 1010;
using namespace std;
int lever_order[N], mid_order[N];
int n;

void dfs(int t, int &k) {
    // 左根右
    if (t * 2 <= n) // 有左子树
        dfs(t * 2, k);
    lever_order[t] = mid_order[k++];
    if (t * 2 + 1 <= n)//有右子树
        dfs(t * 2 + 1, k);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> mid_order[i];
    }
    sort(mid_order, mid_order + n); // 1.排序完就是中序遍历;
    //2.中序走一遍,依次次插入值
    int k = 0;
    dfs(1, k);
    cout << lever_order[1];
    for (int i = 2; i <= n; ++i) {
        cout << " " << lever_order[i];
    }
    cout << endl;
    return 0;
}

1086 Tree Traversals Again

AcWing链接
PAT链接

英语单词

解析
找规律

• 节点被Push, 若上次操作为Push,则它的父节点是上个节点,它为左孩子
• 节点被Push, 若上次操作为Pop,则它的父节点是上个被删除的节点,它为右孩子
  本规律根据非递归的二叉树遍历得到
  注意点

#include 
#include 

const int N = 40;
using namespace std;
int l[N], r[N];

void dfs(int t, int root) {
    if (l[t]) dfs(l[t], root);
    if (r[t]) dfs(r[t], root);
    if (t == root) cout << t;
    else cout << t << " ";
}

int main() {
    int n;
    cin >> n;
    int root;
    int pre = 0, type; // type = 0 上一次是push
    stack s;
    for (int i = 0; i < 2 * n; ++i) {
        string op;
        cin >> op;
        if (op == "Push") {
            int x;
            cin >> x;
            if (!pre) root = x;
            else {
                if (!type) l[pre] = x;
                else r[pre] = x;
            }
            s.push(x);
            pre = x;
            type = 0;
        } else {
            type = 1;
            pre = s.top();
            s.pop();
        }
    }
    dfs(root, root);
    return 0;
}

1099 Build A Binary Search Tree

AcWing链接
PAT链接

解析
与之前的完全二叉搜索树类似
先记录下树的结构
然后将给定的数字排序.即为中序遍历结果
通过一次dfs将二叉搜索树的权值按顺序记录进res数组中
使用一次bfs将二叉搜索树的权值按照层序遍历的方式输出

#include 
#include 

const int N = 110;
using namespace std;
int l[N], r[N];
int value[N], res[N];
int q[N];
int n;

void dfs(int u, int &k) {
    if (u == -1)return;
    dfs(l[u], k);
    res[u] = value[k++];
    dfs(r[u], k);
}

void bfs() {
    int head = 0, tail = 0;
    q[0] = 0;
    while (head <= tail) {
        int t = q[head++];
        if (l[t] != -1) q[++tail] = l[t];
        if (r[t] != -1) q[++tail] = r[t];
    }
    cout << res[0];
    for (int i = 1; i < n; ++i) {
        cout << " " << res[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 >> value[i];
    sort(value, value + n);
    int k = 0;
    dfs(0, k);
    bfs();
    return 0;
}

1102 Invert a Binary Tree

AcWing链接
PAT链接

英语单词

• indices index的复数

解析
多了个二叉树的反转,相当于所有的左子树和右子树交换一下,使用后序dfs来交换,前序也可以,但是中序不行(有些节点会被反转两次)
然后就是普通的dfs和bfs输出

注意点

#include 
#include 
#include 

const int N = 20;
using namespace std;
int n;
int l[N], r[N], q[N];
bool has_father[N];

void dfs_reverse(int t) {
    if (t == -1) return;
    dfs_reverse(l[t]);
    dfs_reverse(r[t]);
    swap(l[t], r[t]);
}

void dfs(int u, int &k) {
    if (u == -1) return;
    dfs(l[u], k);
    if (k++ == n - 1) cout << u;
    else cout << u << " ";
    dfs(r[u], k);
}

void bfs(int root) {
    int head = 0, tail = 0;
    q[0] = root;
    while (head <= tail) {
        int t = q[head++];
        if (l[t] != -1) q[++tail] = l[t];
        if (r[t] != -1) q[++tail] = r[t];
    }
    cout << root;
    for (int i = 1; i < n; ++i) {
        cout << " " << q[i];
    }
    cout << endl;
}

// 层序加中序
int main() {
    cin >> n;
    memset(l, -1, sizeof(l));
    memset(r, -1, sizeof(r));
    for (int i = 0; i < n; ++i) {
        char x, y;
        cin >> x >> y;
        if (x != '-') l[i] = x - '0', has_father[l[i]] = true;
        if (y != '-') r[i] = y - '0', has_father[r[i]] = true;
    }
    int root = 0;
    while (has_father[root]) root++; // 找到第一个没father的节点为根
    dfs_reverse(root);
    int k = 0;
    bfs(root);
    dfs(root, k);
    return 0;
}

模板

AcWing链接
PAT链接

英语单词

解析

注意点