树算法刷题专题

2022-08-14

[[toc]]

1094 The Largest Generation

思路：利用层序遍历对每一层节点进行统计。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 110;

struct node {
    int layer;
    vector<int> child;
}Node[N];

int num[N];
int deepLayer = 0;
void layerOrder(int root){
    queue<int> Q;
    Q.push(root);
    while (!Q.empty()) {
        int front = Q.front();
        Q.pop();
        for (int i = 0; i < Node[front].child.size(); i++) {
            int child = Node[front].child[i];
            Node[child].layer = Node[front].layer + 1;
            num[Node[child].layer]++;
            deepLayer = Node[child].layer;
            Q.push(child);
        }
    }
}
    
int main (int argc, char *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int id, k;
        scanf("%d%d", &id, &k);
        int ID;
        for (int j = 0; j < k; j++) {
            scanf("%d", &ID);
            Node[id].child.push_back(ID);
        }
    }
    fill(num, num + N, 0);
    int root = 1;
    Node[root].layer = 1;
    num[1] = 1;
    layerOrder(root);
    int lagerLayer = 1, lagerNum = 1;
    for (int i = 1; i <= deepLayer; i++) {
        if (num[i] >= lagerNum) {
            lagerNum = num[i];
            lagerLayer = i;
        }
    } 
    printf("%d %d\n", lagerNum, lagerLayer); 
    return 0;
}

注意点：第二个测试点（只有一个根节点的情况）,第三个测试点（节点为最后一个点的情况）

1079 Total Sales of Supply Chain

思路：利用DFS找到根节点的时候，计算价格即可。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 100010;

struct node {
    int data = 0;
    int layer;
    vector<int> child;
}Node[MAXN];

double p, r;
double sum;
void DFS(int root){
    if (Node[root].child.size() == 0) {
        sum += Node[root].data * p * pow(1 + r / 100, Node[root].layer);
        return;
    }
    for (int i = 0; i < Node[root].child.size(); i++) {
        int id = Node[root].child[i];
        Node[id].layer = Node[root].layer + 1;
        DFS(id);
    }
}

int main (int argc, char *argv[])
{
    int n;
    scanf("%d%lf%lf", &n, &p, &r);
    for (int i = 0; i < n; i++) {
        int k;
        int id;
        scanf("%d", &k);
        if (k == 0) {
            scanf("%d", &id);
            Node[i].data = id;
        }
        else {
            for (int j = 0; j < k; j++) {
                scanf("%d", &id);
                Node[i].child.push_back(id);
            }
        }
    }
    Node[0].layer = 0;
    DFS(0);
    printf("%.1f\n", sum);
    return 0;
}
>注意：变量类型为double，使用float有几个测试点过不去。

1090 Highest Price in Supply Chain

思路：BFS找到最下面一层，并记录数量

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int MAXN = 100010;

struct node {
    int layer;
    vector<int> child;
}Node[MAXN];

int n;
double p, r;
int maxLayer = 0, num[MAXN];
void BFS(int root){
    queue<int> Q;
    Q.push(root);
    while (!Q.empty()) {
        int front = Q.front();
        Q.pop();
        for (int i = 0; i < Node[front].child.size(); i++) {
            int child = Node[front].child[i];
            Node[child].layer = Node[front].layer + 1;
            num[Node[child].layer]++;
            maxLayer = Node[child].layer;
            Q.push(child);
        }
    }
}

int main (int argc, char *argv[])
{
    scanf("%d%lf%lf", &n, &p, &r);
    int root;
    fill(num, num + MAXN, 0);
    num[0] = 1;
    for (int i = 0; i < n; i++) {
        int id;
        scanf("%d", &id);
        if (id == -1) {
            root = i;
            Node[i].layer = 0;
        }
        else{
            Node[id].child.push_back(i);
        }
    }
    BFS(root);
    double maxPrice = p * pow(1 + r / 100, maxLayer); 
    printf("%.2f %d\n", maxPrice, num[maxLayer]);
    return 0;
}

注意：根节点数量为1

1106 Lowest Price in Supply Chain

思路：BFS找到根节点最低的层，并记录数量

#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int MAXN = 100010;

struct node {
    int layer;
    vector<int> child;
}Node[MAXN];

int n; 
double p, r;
int lowLayer = 0, num = 0;

int numNode = 0;
void BFS(int root){
    if (Node[root].child.size() == 0) {
        lowLayer = 0;
        num = 1;
        return;
    }
    queue<int> Q;
    Q.push(root);
    while (!Q.empty()) {
        int front = Q.front();
        Q.pop();
        if (Node[front].child.size() == 0 && numNode == 0) {
            lowLayer = Node[front].layer;
            numNode++;
        }
        if (Node[front].child.size() == 0 && Node[front].layer == lowLayer) {
            num++;
        }
        for (int i = 0; i < Node[front].child.size(); i++) {
            int child = Node[front].child[i];
            Node[child].layer = Node[front].layer + 1;
            Q.push(child);
        }
    }
}

int main (int argc, char *argv[])
{
    scanf("%d %lf %lf", &n, &p, &r);
    for (int i = 0; i < n; i++) {
        int k;
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            int id;
            scanf("%d", &id);
            Node[i].child.push_back(id);
        }
    }
    Node[0].layer = 0;
    BFS(0);
    double lowPrice; 
    lowPrice = p * pow(1 + r / 100, lowLayer);
    printf("%.4f %d\n", lowPrice, num);
    return 0;
}

一次过

1004 Counting Leaves

思路：层序遍历找每一层的叶子节点

#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 110;

struct node {
    int layer;
    vector<int> child;
}Node[MAXN];

int num[MAXN];
int maxLayer;
void BFS(int root){
    queue<int> Q;
    Q.push(root);
    while (!Q.empty()) {
        int front = Q.front();
        Q.pop();
        if (Node[front].child.size() == 0) {
            num[Node[front].layer]++;
            maxLayer = Node[front].layer;
        }
        for (int i = 0; i < Node[front].child.size(); i++) {
            int child = Node[front].child[i];
            Node[child].layer = Node[front].layer + 1;
            Q.push(child);
        }
    }
}

int main (int argc, char *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int parent, k;
        scanf("%d%d", &parent, &k);
        int id;
        for (int j = 0; j < k; j++) {
            scanf("%d", &id);
            Node[parent].child.push_back(id);
        }
    }
    fill(num, num + MAXN, 0);
    Node[1].layer = 0;
    BFS(1);
    for (int i = 0; i <= maxLayer; i++) {
        if (i == maxLayer) {
            printf("%d\n", num[i]);
        }
        else {
            printf("%d ", num[i]); 
        }
    }
    return 0;
}

一次过

1086 Tree Traversals Again

#include <cstddef>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int MAXN = 40;

struct node {
    int data;
    node* lchild;
    node* rchild;
};
int n;
vector<int> pre;
vector<int> in;
int num = 1;
void postOrder(node* root){
    if (root == NULL) {
        return;
    }
    postOrder(root->lchild);
    postOrder(root->rchild);
    if(num == n) printf("%d\n", root->data);
    else {num ++;
        printf("%d ", root->data);}
}
node***** create(int preL, int preR, int inL, int inR){
    if (preL > preR) {
        return NULL;
    }
    node* root = new node;
    root->data = pre[preL];
    int k;
    for (k = inL; k <= inR; k++) {
        if (in[k] == pre[preL]) {
            break;
        }
    }
    int leftNum = k - inL;
    root->lchild = create(preL + 1, preL + leftNum, inL, k - 1);
    root->rchild = create(preL + leftNum + 1, preR, k + 1, inR);
    return root;
}

int main (int argc, char *argv[])
{
    scanf("%d", &n);
    int x;
    string str;
    stack<int> st;
    for (int i = 0; i < n * 2; i++) {
        cin >> str;
        if (str == "Push") {
           scanf("%d", &x); 
           pre.push_back(x);
           st.push(x);
        }
        if (str == "Pop") {
            in.push_back(st.top());
            st.pop();
        }
    }
    node* root = create(0, n - 1, 0, n - 1);
    postOrder(root);
    return 0;
}

注意：create函数递归的区间范围

1102 Invert a Binary Tree

思路：层序遍历与中序遍历，每次以右节点为先遍历的点

#include <algorithm>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;
const int MAXN = 20;

vector<int> layer;
vector<int> in;
struct node {
    int lchild = -1;
    int rchild = -1;
}Node[MAXN];

int flag[MAXN];
void layerOrder(int root){
    queue<int> Q;
    Q.push(root);
    while (!Q.empty()) {
        int front = Q.front();
        Q.pop();
        layer.push_back(front);
        if (Node[front].rchild != -1) {
            Q.push(Node[front].rchild);
        }
        if (Node[front].lchild != -1) {
            Q.push(Node[front].lchild);
        }
    }
}

void inOrder(int root){
    if (root == -1) {
        return;
    }
    inOrder(Node[root].rchild);
    in.push_back(root);
    inOrder(Node[root].lchild);
}

int main (int argc, char *argv[])
{
    fill(flag, flag + MAXN, false);
    int n;
    scanf("%d", &n);
    char l, r;
    getchar();
    for (int i = 0; i < n; i++) {
        scanf("%c %c", &l, &r);
        getchar();
        // cin >> l >> r;
        if (l >= '0' && l <= '9') {
            Node[i].lchild = l - '0';
            flag[l - '0'] = true;
        }
        if (r >= '0' && r <= '9') {
            Node[i].rchild = r - '0';
            flag[r - '0'] = true;
        }
    }
    int root;
    for (int i = 0; i < n; i++) {
        if (!flag[i]) {
            root = i;
            break;
        }
    }
    layerOrder(root);
    for (int i = 0; i < n - 1; i++) {
        printf("%d ", layer[i]);
    }
    printf("%d\n", layer[n - 1]);
    inOrder(root);
    for (int i = 0; i < n - 1; i++) {
        printf("%d ", in[i]);
    }
    printf("%d\n", in[n - 1]);
    return 0;
}

注意：用scanf的%c输入时会识别到空格和回车，应用getchar（）读入回车，或者直接使用cin即可。

1064 Complete Binary Search Tree

思路：将输入数据排序即为二叉查找树的中序遍历输出，假设已知CBT树，在中序遍历的时候加入数据，即可完成CBT树，CBT数组中存放的就是树层序输出的结果。

已知中序遍历和完全二叉查找树，求层序遍历。

#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAXN =  1010;

bool cmp(int a, int b){
    return a < b;
}

int CBT[MAXN];
int num[MAXN];

int n;
int Index = 0;
void inOrder(int root){
    if (root > n) {
        return;
    }
    inOrder(root * 2);
    CBT[root] = num[Index++]; 
    inOrder(root * 2 + 1);
}

int main (int argc, char *argv[])
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", num + i);
    }
    sort(num, num + n, cmp);
    inOrder(1);
    for (int i = 1; i < n; i++) {
        printf("%d ", CBT[i]);
    }
    printf("%d\n", CBT[n]);
    return 0;
}

注意

1099 Build A Binary Search Tree

思路：与上题思路一样，已知二叉树结构，和中序遍历的结果，可以在中序遍历的同时插入数据，最后层序输出结果。

 #include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 110;

int num[MAXN];
struct node {
    int data;
    int lchild;
    int rchild;
}Node[MAXN];

bool cmp(int a, int b){
    return a < b;
}

int Index = 0;
void inOrder(int root){
    if (root == -1) {
        return;
    }
    inOrder(Node[root].lchild);
    Node[root].data = num[Index++];
    inOrder(Node[root].rchild);
}

vector<int> layer;
void layerOrder(int root){
    queue<int> Q;
    Q.push(root);
    while (!Q.empty()) {
        int front = Q.front();
        Q.pop();
        layer.push_back(Node[front].data);
        if (Node[front].lchild != -1) {
            Q.push(Node[front].lchild);
        }
        if (Node[front].rchild != -1) {
            Q.push(Node[front].rchild);
        }
    }

}
int main (int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    int id1, id2;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &id1, &id2);
        Node[i].lchild = id1;
        Node[i].rchild = id2;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", num + i);
    }
    sort(num, num + n, cmp);
    inOrder(0);
    layerOrder(0);
    for (int i = 0; i < n - 1; i++) {
        printf("%d ", layer[i]);
    }
    printf("%d\n", layer[layer.size() - 1]);
    return 0;
}

注意: root索引和root.data是不一样的值。

1066 Root of AVL Tree

思路:AVL树的常规操作，代码记住

#include <cstddef>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <sys/errno.h>
using namespace std;
const int  MAXN = 30;

struct node {
    int data;
    int height;
    node* lchild;
    node* rchild;
};

node* newNode(int v){
    node* Node = new node;
    Node->data = v;
    Node->height = 1;
    Node->lchild = NULL;
    Node->rchild = NULL;
    return Node;
}
int getHeight(node* root){
    if (root == NULL) {
        return 0;
    }
    return root->height;
}

int getBalanceFactor(node* root){
    return getHeight(root->lchild) - getHeight(root->rchild);
}

void updataHeight(node* root){
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
void L(node* &root){
    node* temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    updataHeight(root);
    updataHeight(temp);
    root = temp;
}

void R(node* &root){
    node* temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    updataHeight(root);
    updataHeight(temp);
    root = temp;
}

void insert(node* &root, int v){
    if (root == NULL) {
        root = newNode(v);
        return;
    }
    if (v < root->data) {
        insert(root->lchild, v);
        updataHeight(root);
        if (getBalanceFactor(root) == 2) {
            if (getBalanceFactor(root->lchild) == 1) {
                R(root);
            }
            else if (getBalanceFactor(root->lchild) == -1) {
                L(root->lchild);
                R(root);
            }
        }
    }
    else{
        insert(root->rchild, v);
        updataHeight(root);
        if (getBalanceFactor(root) == -2) {
            if (getBalanceFactor(root->rchild) == -1) {
                L(root);
            }
            else if (getBalanceFactor(root->rchild) == 1) {
                R(root->rchild);
                L(root);
            }
        }
    }
}
node* create(int data[], int n){
    node* root = NULL;
    for (int i = 0; i < n; i++) {
        insert(root, data[i]);
    }
    return root;
}

int main (int argc, char *argv[])
{
    int n;
    int num[MAXN];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", num + i);
    }
    node* root = create(num, n);
    printf("%d\n", root->data);
    return 0;
}

思路:将每个爱好对应第一次出现的节点，此后每出现这个爱好，就把人和此节点的根节点合并。最后统计根节点出现的次数，即为每个组的人数，后统计几个组，排序输出结果。

#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
const int N = 1010;

bool cmp(int a, int b){
    return a > b;
}

int father[N];
int hobby[N]; //某个爱好的父节点
int isRoot[N];
int findFather(int x){
    if (x == father[x]) {
       return x; 
    }
    else{
        int F = findFather(father[x]);
        father[x] = F;
        return F;
    }
}

void Union(int a, int b){
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        father[faA] = faB;    
    }
}

void init(int n){
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

int main (int argc, char *argv[])
{
    int n, k, ho;
    scanf("%d", &n);
    fill(hobby, hobby + N, 0);
    fill(isRoot, isRoot + N, 0);
    init(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d:", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &ho);
            if (hobby[ho] == 0) {
                hobby[ho] = i;
            }
            Union(i, findFather(hobby[ho]));
        }
    }
    for (int i = 1; i <= n; i++) {
        isRoot[findFather(i)] ++;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (isRoot[i] != 0) {
            ans ++;
        }
    }
    printf("%d\n", ans);
    sort(isRoot + 1, isRoot + n + 1, cmp);
    for (int i = 1; i <= ans; i++) {
        printf("%d", isRoot[i]);
        if (i < ans) {
            printf(" ");
        }
    }
    return 0;
}

注意：isRoot函数的意义要了解清楚

1098 Insertion or Heap Sort

思路:通过插入排序前面部分有序，第一个无序后的数字与原输入数组保持一致来判断哪种排序方式。
堆排序：从后往前找到第一个小于堆顶的元素，交换，后向下调整。
插入排序：找到第一个要排序的元素，与前面元素进行比较，最终找到插入位置。

#include <stdio.h>
#include <algorithm>
#include <tuple>
using namespace std;
const int N = 110;

//false Insert sort
int k;
bool judgeInsertSort(int a[], int b[], int n){
    for (int i = 2; i <= n; i++) {
        if (b[i] < b[i-1]) {
            k = i;
            break;
        }
    }
    for (int i = k; i <= n; i++) {
        if (a[i] != b[i]) {
            return false;
        }
    }
    return true;
}
void insertOnce(int a[]){
    int temp = a[k];
    int j = k;
    while (j > 1 && temp < a[j - 1]) {
        a[j] = a[j-1];
        j--;
    }
    a[j] = temp;
}

void downAdjust(int low, int high, int a[]){
    int i = low, j = i * 2;
    while (j <= high) {
        if (j + 1 <= high && a[j+1] > a[j]) {
            j = j + 1;
        }
        if (a[j] > a[i]) {
            swap(a[j], a[i]);
            i = j;
            j = i * 2;
        }
        else break;
    }
}

void print(int a[], int n){
    for (int i = 1; i <= n; i++) {
        printf("%d", a[i]);
        if (i < n) {
            printf(" ");
        }
    }
}

void heapOnce(int b[], int n){
    int k;
    for (int i = n; i > 1 ; i--) {
        if (b[i] < b[1]) {
            k = i;
            break;
        }
    }
    swap(b[1], b[k]);
    downAdjust(1, k - 1, b);
}


int main (int argc, char *argv[])
{
    int n;
    int a[N], b[N];
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", b + i);
    }
    if (judgeInsertSort(a, b, n)) {
        printf("Insertion Sort\n");
        insertOnce(b);
        print(b, n);
    }
    else {
        printf("Heap Sort\n");
        heapOnce(b, n);
        print(b, n);
    } 
    return 0;
}

注意：堆排序的头节点对应a[1]非a[0]

1053 Path of Equal Weight

思路：dfs搜索即可，可以把value也作为参数，可以有效剪枝。
注意：算法笔记上的方法排序误，最后一个测试点过不了参考

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 110;

struct node {
    int weight;
    vector<int> child;
}Node[N];

bool cmp(vector<int> a, vector<int> b){
    for (int i = 0; i < min(a.size(), b.size()); i++) {
        if (a[i] > b[i]) {
            return true;
        }
        if (a[i] < b[i]) {
            return false;     
        }
    }
    return false;
}

void printResult(vector<int> v){
    for (int i = 0; i < v.size(); i++) {
        printf("%d", v[i]);
        if (i != v.size() - 1) {
            printf(" ");
        }
    }
    printf("\n");
}

int w;
vector<vector<int> > path;
vector<int> tempPath;
void DFS(int root, int value){
    if (Node[root].child.size() == 0) {
        tempPath.push_back(Node[root].weight);
        value += Node[root].weight;
        if (value == w) {
            path.push_back(tempPath);
        }
        tempPath.pop_back();
    }
    value += Node[root].weight;
    if (value > w) {
        return;
    }
    tempPath.push_back(Node[root].weight);
    for (int i = 0; i < Node[root].child.size(); i++) {
        DFS(Node[root].child[i], value);
    }
    tempPath.pop_back();
    return;
}

int main (int argc, char *argv[])
{
    int n, m;
    scanf("%d%d%d", &n, &m, &w);
    int weight;
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight);
        Node[i].weight = weight;
    }
    int st, end;
    int k;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &st, &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &end);
            Node[st].child.push_back(end);
        }
    }
    DFS(0, 0);
    sort(path.begin(), path.end(), cmp);
    for (int i = 0; i < path.size(); i++) {
        printResult(path[i]);
    }
    return 0;
}

1094 The Largest Generation

1079 Total Sales of Supply Chain

1090 Highest Price in Supply Chain

1106 Lowest Price in Supply Chain

1004 Counting Leaves

1086 Tree Traversals Again

1102 Invert a Binary Tree

1064 Complete Binary Search Tree

1099 Build A Binary Search Tree

1066 Root of AVL Tree

1107 Social Clusters

1098 Insertion or Heap Sort

1053 Path of Equal Weight