AcWing 1259. 二叉树遍历
原题链接
中等
作者:
我要出去乱说
,
2021-02-04 13:22:10
,
所有人可见
,
阅读 393
#include <iostream>
#include <unordered_map>
using namespace std;
bool st[30];
string res;
struct Node
{
char val;
Node *left, *right;
Node(char _val) : val(_val), left(NULL), right(NULL) {}
};
void dfs(Node *root) //前序遍历
{
if (!root) return;
res += root->val;
dfs(root->left);
dfs(root->right);
}
int main()
{
string inorder, lorder; //inorder:中序遍历, lorder:层序遍历
cin >> inorder >> lorder;
unordered_map<char, int> pos; //将中序遍历录入哈希表
for (int i = 0; i < inorder.size(); i ++ ) pos[inorder[i]] = i; //中序遍历能判断左右子树大小
Node* q[30]; //通过层序遍历还原二叉树结构
q[0] = new Node (lorder[0]); //lorder[0]为根节点
for (int i = 0, j = 1; j < lorder.size();) //按层遍历,i是当前层起点,j是下层起点
{
for (int end = j; i < end; i ++ ) //遍历当前层,注意这两层循环中i和j都是不断递增的,没有重置回0
{
int p = pos[lorder[i]]; //当前节点的位置
st[p] = true;
//判断左儿子是否存在
if (p && !st[p - 1]) //p不等于0且p-1没有被用过
{
q[i]->left = new Node(lorder[j]); //q[i]的左儿子属于下一层,而下一层的起点是j
q[j ++ ] = q[i]->left; //给q[i]的左儿子q[j]赋值
}
//判断右儿子是否存在
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;
}