P1305 新二叉树——题解

解题思路

用两个字符数组分别保存每个字母结点的左孩子和右孩子。记住第一条记录中的结点就是根，然后从根开始递归：先输出当前结点，再递归访问左孩子，最后递归访问右孩子。遇到 * 立即返回。

正确性说明

递归函数严格按照根、左、右的顺序执行，所以输出顺序就是前序遍历；每个非空孩子继续使用同样规则处理，因此整棵树都会且只会被访问一次。

复杂度分析

每个结点恰好访问一次，时间复杂度 $O(n)$，额外递归空间 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
char lc[130], rc[130];
void dfs(char x){
    if(x=='*') return;
    cout<<x;
    dfs(lc[(int)x]);
    dfs(rc[(int)x]);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin>>n;
    char root='*';
    for(int i=0;i<n;i++){
        char a,b,c; cin>>a>>b>>c;
        if(i==0) root=a;
        lc[(int)a]=b; rc[(int)a]=c;
    }
    dfs(root);
    return 0;
}

#include <bits/stdc++.h> using namespace std; char lc[130], rc[130]; void dfs(char x){ if(x=='') return; cout<<x; dfs(lc[(int)x]); dfs(rc[(int)x]); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; char root=''; for(int i=0;i<n;i++){ char a,b,c; cin>>a>>b>>c; if(i==0) root=a; lc[(int)a]=b; rc[(int)a]=c; } dfs(root); return 0; }