PAT 刷题笔记

2022.8.2
C++ 时分秒转换

#include <iostream>
using namespace std;

int main()
{
    
    int val;
    cin >> val;
    int hh = val / 3600;
    int mm = val / 60 % 60;
    int ss = val % 60;
    printf("%02d:%02d:%02d\n", hh, mm, ss);
    return 0;
}

2022.8.3
树与二叉树

#include <iostream>
#include <queue>
#include <map>
using namespace std;

struct node
{
    
    int data;
    node *left;
    node *right;
}; // 定义二叉树节点

const int N = 31;
int n, in[N], pre[N], post[N];

// 已知后序遍历和中序遍历，求前序遍历
void preOrder(int root, int start, int end)
{
    
    if (start > end)
    {
    
        return;
    }
    int i = start; // 保存根节点在中序序列中的位置
    while (i < end && in[i] != post[root])
    {
    
        i++;
    }
    printf("%d ", post[root]);                    // 中左右
    preOrder(root - (end - i + 1), start, i - 1); // 画图
    preOrder(root - 1, i + 1, end);
}

// 已知前序遍历和中序遍历，求后序遍历
void postOrder(int root, int start, int end)
{
    
    if (start > end)
    {
    
        return;
    }
    int i = start; // 保存根节点在中序序列中的位置
    while (i < end && in[i] != pre[root])
    {
    
        i++;
    }
    postOrder(root + 1, start, i - 1); // 画图
    postOrder(root + 1 + i - start, i + 1, end);
    printf("%d ", pre[root]); //左右中
}

node *createTree(int postL, int postR, int inL, int inR)
{
    
    if (postL > postR)
    {
    
        return nullptr;
    }
    node *root = new node;
    root->data = post[postR];

    int k; //求根节点在中序序列中的位置
    for (k = inL; k <= inR; k++)
    {
    
        if (in[k] == post[postR])
        {
    
            break;
        }
    }
    int num_left = k - inL; // 左子树节点个数
    root->left = createTree(postL, postL + num_left - 1, inL, k - 1);
    root->right = createTree(postL + num_left, postR - 1, k + 1, inR);
    return root; // 返回根节点
}

void bfs(node *root)
{
    
    queue<node *> q;
    node *p = root;
    q.push(p);

    int num = 0; //记录已访问节点个数
    while (!q.empty())
    {
    
        p = q.front();
        q.pop();
        num++;
        printf("%d", p->data); // 访问p节点
        if (num < n)
        {
    
            printf(" ");
        }
        if (p->left != nullptr)
        {
    
            q.push(p->left);
        }
        if (p->right != nullptr)
        {
    
            q.push(p->right);
        }
    }
    printf("\n");
}

// 方法二
map<int, int> level;
void pre2(int root, int start, int end, int idx)
{
    
    if (start > end)
    {
    
        return;
    }
    int i = start;
    while (i < end && in[i] != post[root])
    {
    
        i++;
    }
    level[idx] = post[root]; // visit;
    pre2(root - (end - i + 1), start, i - 1, 2 * idx + 1);
    pre2(root - 1, i + 1, end, 2 * idx + 2);
}

int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i++)
    {
    
        scanf("%d", &post[i]);
    }
    for (int i = 0; i < n; i++)
    {
    
        scanf("%d", &in[i]);
    }
    // 方法一
    // node *root = createTree(0, n - 1, 0, n - 1);
    // bfs(root); //层次序遍历

    // 方法二
    pre2(n - 1, 0, n - 1, 0);
    auto it = level.begin();
    printf("%d", it->second);
    while (++it != level.end())
    {
    
        printf(" %d", it->second);
    }
    return 0;
}