洛谷 P1305：新二叉树 ← DFS + 哈希表优化
【题目来源】
https://www.luogu.com.cn/problem/P1305【题目描述】
输入一串二叉树，输出其前序遍历。【输入格式】
第一行为二叉树的节点数 n。(1≤n≤26)
后面 n 行，第一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。
空节点用 * 表示。【输出格式】
二叉树的前序遍历。【输入样例】
6
abc
bdi
cj*
d**
i**
j**【输出样例】
abdicj【数据范围】
1≤n≤26【算法分析】
● 在 C++ 中，std::vector 是一个动态数组容器，默认构造时其大小为 0，且不包含任何元素。直接使用下标运算符 tr[i] 访问未分配内存的位置会导致未定义行为（通常是段错误 Segmentation Fault 或程序崩溃），因为该内存地址并不属于当前 vector 的管理范围。修正方法之一为在访问前，利用 tr.resize(n); 调整 vector 的大小。● 算法代码一：纯 vector 写法，时间复杂度为 O(n^2) → 不能处理重复字符
本题若用如下纯 vector 的写法，时间复杂度为 O(n^2)，能过。但要注意，其仅适用于 n 很小（n<1000）情况。#include
using namespace std;int n;
vector tr; //treevoid dfs(char x) {if(x=='*') return;for(int i=0; i>n;tr.resize(n);for(int i=0; i>tr[i];}dfs(tr[0][0]);return 0;
}/*
in:
6
abc
bdi
cj*
d**
i**
j**out:
abdicj
*/在上述纯 vector 的实现代码中，为什么必须加 if(tr[i]==x)？这个判断语句的核心作用是建立“节点值”与“存储位置”之间的映射关系。● 算法代码二：哈希表写法，时间复杂度为 O(n) → 不能处理重复字符
本代码利用哈希表（Hash Map）实现快速索引，从而将算法效率提升了一个数量级。这是处理树形结构遍历问题时，常用的标准优化手段。#include
using namespace std;unordered_map indexMap;
vector tr;
int n;void dfs(char x) {if(x=='*') return;int i=indexMap[x];cout<>n;tr.resize(n);for(int i=0; i>tr[i];indexMap[tr[i][0]]=i;}dfs(tr[0][0]);return 0;
}/*
in:
6
abc
bdi
cj*
d**
i**
j**out:
abdicj
*/但要注意，如上所示的哈希表优化的写法，要求每行输入的字符串中不能有重复的字符。这是因为，只要输入的字符串中有重复字符，哈希表映射 char → index 就会被覆盖，会直接报错！也就是说，无重复字符时可以用哈希表，有重复字符时禁止用哈希表，必须用“下标递归 + 遍历找孩子”。● 算法代码三：结构体写法，时间复杂度为 O(n^2) → 能够处理重复字符
鉴于此，就有了如下更通用的代码，既适用于无重复字符的情况，又适用于有重复字符的情况。但是，时间复杂度达到 O(n^2)。#include
using namespace std;const int N=30;
struct Node {char val;int le,ri;
} tr[N]; //treevoid dfs(int u) {if(u==-1) return;cout< v;int n;cin>>n;v.resize(n);for(int i=0; i>v[i];tr[i].val=v[i][0];tr[i].le=-1;tr[i].ri=-1;}for(int i=0; i
using namespace std;const int N=30;
struct Node {char val;int le,ri;
} tr[N];/*character -> subscripts
Supports repeated characters*/
vector> pos;void dfs(int u) {if(u==-1) return;cout< v;int n;cin>>n;v.resize(n);for(int i=0; i>v[i];tr[i].val=v[i][0];tr[i].le=-1;tr[i].ri=-1;pos[v[i][0]].push_back(i); //key}for(int i=0; i