UVA 536 Tree Recovery 二叉树重建（重建二叉树+DFS）

一时失言乱红尘 2024-02-17 19:05 66阅读 0赞

本题起初采用的是二叉树重建+dfs完成，然后看见网上不用建树也可以完成，也尝试了这种方法

通过中序遍历和先序遍历（或后序遍历）可以重建二叉树，AC代码如下：

二叉树重建+DFS:

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=26+2;
    char pre_order[maxn],in_order[maxn]; //先序、中序 
    int lch[maxn],rch[maxn];   //储存左右节点 
    int build_tree(int L1,int R1,int L2,int R2){
    	if(L1>R1)return 0; //空树 
    	int root=pre_order[L1]-'A'+1;
    	int p=L2;
    	while((in_order[p]-'A'+1)!=root)p++;
    	int cnt=p-L2; //左子树的结点个数
    	lch[root]=build_tree(L1+1,L1+cnt,L2,p-1); 
    	rch[root]=build_tree(L1+cnt+1,R1,p+1,R2);
    	return root;
    }
    void dfs(int cur){
    	if(!lch[cur] && !rch[cur]){   //没有左右子节点（叶子） 
    		printf("%c",cur+'A'-1);
    		return ;
    	}
        if(lch[cur])dfs(lch[cur]);
    	if(rch[cur])dfs(rch[cur]);
    	printf("%c",cur+'A'-1); 
    }
    int main(){
        while(scanf("%s%s",pre_order,in_order)==2){
        	int len=strlen(pre_order);
            build_tree(0,len-1,0,len-1);
        	dfs(pre_order[0]-'A'+1);
        	printf("\n");
    	}
    	return 0;
    }

递归：

#include<cstdio>
    #include<cstring> 
    using namespace std;
    const int maxn=26+2;
    char pre_order[maxn],in_order[maxn];
    void solve(int L1,int R1,int L2,int R2){
    	if(L1>R1)return ;
    	char root =pre_order[L1]; 
    	int p=L2; 
    	while(in_order[p]!=root)p++;
    	int cnt=p-L2;  //左子结点的个数 
    	solve(L1+1,L1+cnt,L2,p-1);
    	solve(L1+cnt+1,R1,p+1,R2);
    	printf("%c",root);
    }
    int main(){
    	while(scanf("%s%s",pre_order,in_order)==2){
    		int len=strlen(pre_order);
    		solve(0,len-1,0,len-1);
    		printf("\n"); 
    	}
    	return 0;
    }