Skip to main content

4274.后缀表达式

caution

原题链接：https://www.acwing.com/problem/content/4277/

思路​

看题，跟树有关，肯定要用到树的遍历。题目已经给出了中缀表达式的树，所以对其进行后序遍历即可。但从样例发现，不能只进行单纯的后序遍历，需要针对不同的情况进行考虑。

  1. 左子树和右子树同时为空：输出节点的值
  2. 左子树为空，右子树非空：输出节点的值，遍历右子树
  3. 左子树和右子树均非空：遍历左子树，遍历右子树，输出节点值
  4. 左子树非空，右子树为空：因为中缀表达式不会出现这种情况，故不用考虑

题目没有给出根节点在哪，但是从样例很容易发现，根节点就是输入样例当中未出现过的节点的编号，所以用一个哈希即可找到未出现的节点编号。

最后只要建好树，利用递归遍历即可。

代码​

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

int n;
unordered_map<int, bool> s;

struct Node {
    string data;
    int l, r;
} g[N];

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

    cout << "(";
    if (g[u].l == -1 && g[u].r == -1)
        cout << g[u].data;
    else if (g[u].l == -1 && g[u].r != -1) {
        cout << g[u].data;
        dfs(g[u].r);
    } else {
        dfs(g[u].l);
        dfs(g[u].r);
        cout << g[u].data;
    }
    cout << ")";
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> g[i].data >> g[i].l >> g[i].r;
        s[g[i].l] = true;
        s[g[i].r] = true;
    }

    int head;
    for (int i = 1; i <= n; i++) {
        if (s.count(i) == 0) {
            head = i;
            break;
        }
    }

    dfs(head);

    return 0;
}