1 条题解

  • 0
    @ 2024-12-24 9:59:30

    C :

    #include <stdio.h>
    #include <string.h>
    void build(char *pre,char *in,int len){
    	if (len<=0)
    	{
    		return ;
    	}
    	int pos=strchr(in,*pre)-in;
    	build(pre+1,in,pos);
    	build(pre+pos+1,in+pos+1,len-pos-1);
    	printf("%c",*pre);
    
    }
    int main(){
    	char pre[1000],in[1000];
    //	freopen("1.txt","r",stdin);
    	while (scanf("%s %s",pre,in)!=EOF)
    	{
    		build(pre,in,strlen(pre));
    		printf("\n");
    	}
    //	fclose(stdin);
    	return 0;
    }
    

    C++ :

    #include<cstdio>
    #include<iostream>
    #include<string>
    using namespace std;
    
    struct BT
    {
    	char data;
    	BT *lchild,*rchild;
    };
    
    BT *build(string preorder,string inorder)
    {
    	BT *root;
    	int p;
    	if(!preorder.length())
    		root=NULL;
    	else
    	{
    		root=new BT;
    		root->data=preorder[0];
    		p=inorder.find(root->data);
    		root->lchild=build(preorder.substr(1,p),inorder.substr(0,p));
    		root->rchild=build(preorder.substr(1+p),inorder.substr(p+1));
    	}
    	return root;
    }
    
    void postorder(BT *root)
    {
    	if(root)
    	{
    		postorder(root->lchild);
    		postorder(root->rchild);
    		putchar(root->data);
    	}
    }
    
    int main()
    {
    	string preorder,inorder;
    	BT *root;
    	while(cin>>preorder>>inorder)
    	{
    		root=build(preorder,inorder);
    		postorder(root);
    		printf("\n");
    	}
    	return 0;
    }
    

    Java :

    import java.util.Scanner;
    
    public class Main {
    	public static void main(String args[]) {
    		Scanner jin = new Scanner(System.in);
    		while (jin.hasNext()) {
    			String pre = jin.next(), mid = jin.next();
    			Node root = new Node(pre);
    			root.build(pre, mid);
    			root.post();
    			System.out.println();
    		}
    	}
    }
    
    class Node {
    	char entry;
    	Node lson;
    	Node rson;
    
    	public Node(String pre) {
    		entry = pre.charAt(0);
    		lson = null;
    		rson = null;
    	}
    
    	public void build(String pre, String mid) {
    		if (pre.length() > 1) {
    			int p = mid.indexOf(entry);
    			String lmid = mid.substring(0, p);
    			String rmid = mid.substring(p + 1);
    			String lpre = pre.substring(1, 1 + lmid.length());
    			String rpre = pre.substring(1 + lmid.length());
    			if (lpre.length() > 0) {
    				lson = new Node(lpre);
    				lson.build(lpre, lmid);
    			}
    			if (rpre.length() > 0) {
    				rson = new Node(rpre);
    				rson.build(rpre, rmid);
    			}
    		}
    	}
    
    	public void post() {
    		if (lson != null)
    			lson.post();
    		if (rson != null)
    			rson.post();
    		System.out.print(entry);
    	}
    }
    
    • 1

    信息

    ID
    1654
    时间
    1000ms
    内存
    32MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者