3598.二叉树遍历

caution

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

思路

二叉树遍历的类型最主要是找到根所在的位置，那么可以通过递归来遍历二叉树。

注意二叉树四种遍历的顺序：

1. 先序遍历——$根结点\rightarrow左子树\rightarrow右子树$
2. 中序遍历——$左子树\rightarrow根结点\rightarrow右子树$
3. 后序遍历——$右子树\rightarrow左子树\rightarrow根结点$
4. 层序遍历——利用队列存储每一层的结点，然后将结点出队的同时，将其左右子树加入，当队列为空是遍历结束。

先序遍历根放在每一个子树对应数组位置的第一个，中序遍历的根放在每个子树对应数组位置的中间位置。分别递归先序遍历和中序遍历的两个序列，找到根节点的位置就可以知道剩下的子树在哪。

代码

#include <bits/stdc++.h>

using namespace std;

// 本题主要考察对于先序和中序的理解

void dfs(string pre, string mid) {
    if (pre.empty())
        return;

    char root = pre[0];
    int k = mid.find(root);  // 找到根节点的下标

    // 先序遍历左子树，因为根节点在下标 0 的位置，所以从下标为 1 开始截取。
    // 中序遍历左子树，因为根节点在中间的位置，所以只需要截取 [0, k] 这一段即可
    dfs(pre.substr(1, k), mid.substr(0, k));
    // 先序遍历右子树，因为之前已经截取 [1, k] 了，所以剩下的就是右子树的部分
    // 中序遍历右子树，因为之前已经截取 [0, k] 的位置，根节点在 k
    // 的位置，所以截取剩下的就是右子树的部分。
    dfs(pre.substr(k + 1), mid.substr(k + 1));
    cout << root;
}

int main() {
    string pre, mid;

    while (cin >> pre >> mid) {
        dfs(pre, mid);
        cout << endl;
    }

    return 0;
}