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

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

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

今日刷题列表

• 1110 Complete Binary Tree
• 1115 Counting Nodes in a Binary Search Tree
• 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

1110 Complete Binary Tree

AcWing链接
PAT链接

注意点

• 一开始在读入节点的时候我用了char和a-'0'来存储,因为粗心没看到题目中可能出现大于10的节点编号,后来改为string就可以了
• stoi()可以很方便的把string类型的字符串转为int

#include 
#include 
#include 

const int N = 30;
using namespace std;
int l[N], r[N];
int n, last_idx, last_node, root = 0;
bool is_father[N];

void dfs(int u, int k) {
    // u代表当前节点,k代表完全二叉树中的节点
    if (u == -1) return;
    if (k > last_idx) {
        last_idx = k;
        last_node = u;
    }
    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));
    for (int i = 0; i < n; ++i) {
        string a, b;
        cin >> a >> b;
        if (a != "-") l[i] = stoi(a), is_father[l[i]] = true;
        if (b != "-") r[i] = stoi(b), is_father[r[i]] = true;
    }
    while (is_father[root]) root++;
    dfs(root, 1);
    if (last_idx == n) cout << "YES " << last_node;
    else cout << "NO " << root;
    return 0;
}

1115 Counting Nodes in a Binary Search Tree

AcWing链接
PAT链接

注意点

• 这边在插入的时候使用&u, 可以更新一开始传人的root值,也可以改变之后递归中l[u],r[u]的值

#include 
#include 

using namespace std;
const int N = 1010;
int l[N], r[N], val[N], idx = 0;
int cnt[N];
int max_depth;

void insert(int &u, int w) {
    if (u == 0) {
        u = ++idx;
        cout << "u = " << u << endl;
        val[u] = w;
    } else if (w <= val[u]) insert(l[u], w);
    else insert(r[u], w);
}

void dfs(int root, int depth) {
    if (root == 0) return;
    max_depth = max(depth, max_depth);
    cnt[depth]++;
    dfs(l[root], depth + 1);
    dfs(r[root], depth + 1);
}

int main() {
    int n;
    cin >> n;
    int root = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        insert(root, x);
        cout << root << endl;
        cout << "*****************" << endl;
    }
    dfs(root, 0);
    int n1 = cnt[max_depth];
    int n2 = cnt[max_depth - 1];
    printf("%d + %d = %dn", n1, n2, n1 + n2);
    return 0;
}

!!! 1119 Pre- and Post-order Traversals

AcWing链接
PAT链接

英语单词

解析
难点在与递归以及暴力遍历前序遍历的序列,找左右的分界点.

#include 
#include 

const int N = 40;
using namespace std;
int pre[N], post[N];

int dfs(int prel, int prer, int postl, int postr, string &s) {
    if (prel > prer) return 1;
    if (pre[prel] != post[postr]) return 0;
    int cnt = 0;
    for (int i = prel; i <= prer; ++i) {
        string lin, rin;
        int lcnt = dfs(prel + 1, i, postl, postl + i - prel - 1, lin);
        int rcnt = dfs(i + 1, prer, postl + i - prel, postr - 1, rin);
        if (lcnt && rcnt) {
            s = lin + to_string(pre[prel]) + " " + rin;
            cnt += lcnt * rcnt;
            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("Yes");
    else puts("No");
    res.pop_back();
    puts(res.c_str());
    return 0;
}

1127 ZigZagging on a Tree

AcWing链接
PAT链接

英语单词

• naive 天真
• alternating 交替的,交互的
  解析
  与1020题类似,只不过这道题在层序遍历的时候要按层数选择反转后记录当前的遍历序列
  注意点
  l.count(t)找的是哈希表l中键为t的个数,如果存在的话再把l[t]加入队列

#include 
#include 
#include 
#include 

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

int build(int il, int ir, int pl, int pr) {
    int root = post[pr];
    int k = pos[root];
    if (il < k) l[root] = build(il, k - 1, pl, pl + k - 1 - il);
    if (k < ir) r[root] = build(k + 1, ir, pl + k - il, pr - 1);
    return root;
}

void bfs(int root) {
    q[0] = root;
    int head = 0, tail = 0;
    int step = 0;
    while (head <= tail) {
        int cur_head = head, cur_tail = tail;
        while (head <= cur_tail) {
            int t = q[head++];
            if (l.count(t)) q[++tail] = l[t];
            if (r.count(t)) q[++tail] = r[t];
        }
        if (++step % 2 == 1) reverse(q + cur_head, q + cur_tail + 1);
    }
    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 >> inorder[i], pos[inorder[i]] = i;
    for (int i = 0; i < n; ++i) cin >> post[i];
    int root = build(0, n - 1, 0, n - 1);
    bfs(root);
    return 0;
}

1138 Postorder Traversal

AcWing链接
PAT链接

注意点

没使用哈希表的写法,能过测试点,但是测试点4花了341 ms

#include 

const int N = 50010;
using namespace std;
int pre[N], in[N];
int l[N], r[N];
int n;
int post = 0, flag = 1;

void build(int il, int ir, int pl, int pr) {
    if (flag == 0) return;
    int root = pre[pl];
    int k;
    for (int i = il; i <= ir; ++i) {
        if (in[i] == root) {
            k = i;
            break;
        }
    }
    if (il < k) build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
    if (k < ir) build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
    if (post == 0) {
        post = root;
        cout << post;
        flag = 0;
        return;
    }
}

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

使用了哈希表的写法,测试点4只花了34 ms

#include 
#include 

const int N = 50010;
using namespace std;
int pre[N], in[N];
unordered_map l, r, pos;
int n;
int post = 0, flag = 1;

void build(int il, int ir, int pl, int pr) {
    if (flag == 0) return;
    int root = pre[pl];
    int k = pos[root];
    if (il < k) build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
    if (k < ir) build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
    if (post == 0) {
        post = root;
        cout << post;
        flag = 0;
        return;
    }
}

int main() {
    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);
    return 0;
}

1066 Root of AVL Tree

AcWing链接
PAT链接

英语单词

• differ by 相差

解析
下图我画出了二叉树右旋的过程,左旋反一下就好

注意点

• height_differ(r[u]) == -1计算右子树那边该不该左旋的时候一个r和l写错了,找了半天bug
• 主要考点还是该不该旋, 理解上图即可

#include 

const int N = 30;
using namespace std;
int l[N], r[N], v[N], h[N], idx;

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;
}

int height_differ(int u) {
    // 计算左右子树的差
    return h[l[u]] - h[r[u]];
}


void insert(int &u, int w) {
    if (!u) {
        u = ++idx;
        v[u] = w;
    } else if (w < v[u]) {
        // 插入左子树
        insert(l[u], w);
        // 检查是否要旋
        if (height_differ(u) == 2) {
            // 插入左子树之后可能造成左子树高度多一些
            if (height_differ(l[u]) == 1) {
                // 左子树的左子树高于右子树, 直接右旋即可
                R(u);
            } else {
                // 左子树的右子树高于左子树的左子树,先左旋再右旋
                L(l[u]);
                R(u);
            }
        }
    } else {
        // 插入右子树
        insert(r[u], w);
        // 检查是否要旋
        if (height_differ(u) == -2) {
            // 插入右子树之后可能造成右子树高度多一些
            if (height_differ(r[u]) == -1) {
                // 右子树的右子树高于左子树, 直接左旋即可
                L(u);
            } else {
                // 右子树的左子树高于右子树的右子树,先右旋再左旋
                R(r[u]);
                L(u);
            }
        }
    }
    update(u);
}

int main() {
    int n, root = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int w;
        cin >> w;
        insert(root, w);
    }
    cout << v[root] << endl;
    return 0;
}

1123 Is It a Complete AVL Tree

AcWing链接
PAT链接

解析

• 综合基础题,其中构建平衡二叉树的过程和上一题一模一样
• 在实现层序遍历的过程中,使用pos来记录每个节点的下标(是他们父亲节点的两倍或者两倍+1) 判断下表是否超过n, 如果n个节点的下标都没超过n,那么一定是完全二叉树.

#include 
#include 
#include 
#include 


const int N = 30;
using namespace std;
int n;
int l[N], r[N], v[N], h[N], idx;
int q[N], pos[N];

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

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

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

int differ_height(int u) {
    // 返回左右子树高度差
    return h[l[u]] - h[r[u]];
}

void insert(int &u, int w) {
    if (!u) {
        u = ++idx;
        v[u] = w;
    } else if (w < v[u]) {
        //插入左
        insert(l[u], w);
        if (differ_height(u) == 2) {
            if (differ_height(l[u]) == 1) R(u);
            else L(l[u]), R(u);
        }
    } else {
        insert(r[u], w);
        if (differ_height(u) == -2) {
            if (differ_height(r[u]) == -1) L(u);
            else R(r[u]), L(u);
        }
    }
    update(u);
}

bool bfs(int root) {
    q[0] = root;
    int k = 1;
    pos[root] = 1;
    int head = 0, tail = 0;
    while (head <= tail) {
        int t = q[head++];
        if (pos[t] > n) return false;
        if (l[t]) q[++tail] = l[t], pos[l[t]] = 2 * pos[t];
        if (r[t]) q[++tail] = r[t], pos[r[t]] = 2 * pos[t] + 1;
    }

    return true;
}

int main() {
    cin >> n;
    memset(h, -1, sizeof(h));
    int root = 0;
    for (int i = 0; i < n; ++i) {
        int w;
        cin >> w;
        insert(root, w);
    }
    bool res = bfs(root);
    cout << v[q[0]];
    for (int i = 1; i < n; ++i) {
        cout << ' ' << v[q[i]];
    }
    cout << endl;
    if (res) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

!!! 1135 Is It A Red-Black Tree

AcWing链接
PAT链接

英语单词

• simple paths 简单路径
• descendant leaves 后代节点

注意点

• 在构建平衡二叉树的过程中判断是否为红黑树

#include 
#include 
#include 

const int N = 40;
using namespace std;
int n, k;
int pre[N], in[N];
unordered_map pos;
bool res;


int build(int il, int ir, int pl, int pr, int &sum) {
    int root = pre[pl];
    int index = pos[abs(root)];
    if (index > ir || index < il) {
        res = false;
        return 0;
    }
    int left = 0, right = 0, left_sum = 0, right_sum = 0;
    if (il < index) left = build(il, index - 1, pl + 1, pl + 1 + index - 1 - il, left_sum);
    if (index < ir) right = build(index + 1, ir, pl + 1 + index - 1 - il + 1, pr, right_sum);
    if (left_sum != right_sum) res = false;
    sum = left_sum;
    if (root < 0) {
        if (left < 0 || right < 0) res = false;
    } else sum++;
    return root;
}

int main() {
    cin >> k;
    while (k--) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> pre[i];
            in[i] = abs(pre[i]);
        }
        sort(in, in + n);
        pos.clear();
        for (int i = 0; i < n; ++i) {
            pos[in[i]] = i;
        }
        res = true;
        int sum = 0;
        int root = build(0, n - 1, 0, n - 1, sum);
        if (root < 0) res = false;
        if (res) puts("Yes");
        else puts("No");
    }
    return 0;
}

模板

AcWing链接
PAT链接

英语单词

解析

注意点