AcWing 1259. 二叉树遍历

题目

树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。

假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。

输入格式

两行，每行是由大写字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。

输出格式

一行，表示二叉树的先序序列。

数据范围

输入字符串的长度均不超过26。

输入样例：

DBEAC
ABCDE

输出样例：

ABDEC

题解

#include <iostream>
#include <unordered_map>

using namespace std;

struct Node
{
    char val;
    Node *left, *right;
    Node(char _val) : val(_val), left(NULL), right(NULL) {}
};

string res;
bool st[30];

void dfs(Node *root)
{
    if (!root) return;
    res += root -> val;
    dfs(root -> left);
    dfs(root -> right);
}

int main()
{
    string inorder, lorder;
    cin >> inorder >> lorder;

    unordered_map<char, int> map;

    for (int i = 0; i < inorder.size(); ++ i) map[inorder[i]] = i;


    Node* q[30];
    q[0] = new Node(lorder[0]);
    for (int i = 0, j = 1; j < lorder.size();)
    {
        for (int end = j; i < end; ++ i)
        {
            int p = map[lorder[i]]; // 查出根节点的下标
            st[p] = true;
            if (p && !st[p - 1]) // 存在左子树
            {
                q[i] -> left = new Node(lorder[j]);
                q[j ++ ] = q[i] -> left;
            }
            if (p + 1 < lorder.size() && !st[p + 1]) //存在右子树
            {
                q[i] -> right = new Node(lorder[j]);
                q[j ++ ] = q[i] -> right;
            }
        }
    }

    dfs(q[0]);

    cout << res << endl;

    return 0;
}