题目链接：P1305 新二叉树 - 洛谷 | 计算机科学教育新生态
题目难度：普及
刷题心得：做了几道这种类型的题都不用建树就可以解决，基本上还是利用好树的结构，例如这道题求前序序列（根左右）是可以用递归来求的。无非就是先从根出发，递归遍历左子树，递归遍历右子树，遇到 * 直接返回就行了。
下面奉上代码部分：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//const int N = 1e6 + 10;
char h,h1; //定义两个是为了将根节点做完参数直接传入函数
int n;
struct node
{
char leftNode,rightNode;//存左右子树的节点
}lt[130];// ASCII 范围是足够的
void dfs(char x)//递归求前序遍历
{
if(x == '*' ) return; 如果是空节点，返回
cout<<x;//输出
dfs(lt[x].leftNode);//递归遍历左子树
dfs(lt[x].rightNode);//递归遍历右子树
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
cin >> h1;
cin >> lt[h1].leftNode >> lt[h1].rightNode;
for(int i=2; i<=n; i++)
{
cin >> h;
cin >> lt[h].leftNode;
cin >> lt[h].rightNode;
}
dfs(h1);
return 0;
}
下面讲讲递归是如何执行的（个人理解）
1. 初始调用：dfs(a)
- 当前节点
a。 - 输出
a。 - 递归访问左子树：
dfs(b)。
2. 递归调用：dfs(b)
- 当前节点
b。
- 输出
b。 - 递归访问左子树：
dfs(d)。
3. 递归调用：dfs(d)
- 当前节点
d。 - 输出
d。 d没有左右子树，所以返回。
4. 回到 b，继续递归访问右子树：dfs(i)
- 当前节点
i。 - 输出
i。 i没有左右子树，所以返回。
5. 回到 a，继续递归访问右子树：dfs(c)
- 当前节点
c。 - 输出
c。 - 递归访问左子树：
dfs(j)。
6. 递归调用：dfs(j)
- 当前节点
j。 - 输出
j。 j没有左右子树，所以返回。
7. 返回到 c，继续递归访问右子树：dfs(*)
- 右子树是空的，所以直接返回。
8. 完成所有递归，结束遍历。
输出：
最终的输出是前序遍历的结果：
abdcij