根据后序和中序遍历输出先序遍历

悠悠 2022-09-27 06:33 113阅读 0赞

字节跳动校招内推码: C4BDSMC
    投递链接: https://job.toutiao.com/s/J691fRK
    内推交流QQ群：1049175720

think:  
1自己或许应该转变思想，自己一直将树的部分当做一种结构来记忆使用，但基本经常出现错误，或许树的知识点也应该作为一种解决问题的思想来理解，而不是一再的死记硬背模板，要学会灵活的变通和变化模板，使其具有生气，自己关于树的遍历部分可能因为自己不自信因此死记模板而不知道灵活变通，导致很多题目很容易犯错误，再次打击自信，所以形成了现在一种看见树就畏惧不自信的心态，自己应该战胜自己，失败并不可怕，可贵的是拥有一颗不断渴望战胜自己的内心，反省才使得自己有了客观理性分析自己的机会，逐渐学会客观全面的看待自己，相信自己，战胜自己，用那份可贵的渴望是自己不断地追求优秀，没有人相伴的时候自己一个人加油往前冲，加油  
2反思：题目自己用链表建树的时候错误在右子树的建立，新的中序遍历数组和新的后序遍历数组初始位置不对

11 根据后序和中序遍历输出先序遍历 (25分)

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。  
输入格式:

第一行给出正整数NNN(≤30\\le 30≤30)，是树中结点的个数。随后两行，每行给出NNN个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。  
输出格式:

在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。  
输入样例:

7  
2 3 1 5 7 6 4  
1 2 3 4 5 6 7

输出样例:

Preorder: 4 1 3 2 6 5 7

以下为答案正确代码——链表建树

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
    	int Data;
    	struct node *left;
    	struct node *right;
    }BinTree;
    
    BinTree * Build(int n, int *mid, int *last);
    void First(BinTree *rt);
    
    int main()
    {
    	int mid[44], last[44];
    	int n, i;
    	BinTree *rt = NULL;
    	scanf("%d", &n);
    	for(i = 0; i < n; i++)
    		scanf("%d", &last[i]);
    	for(i = 0; i < n; i++)
    		scanf("%d", &mid[i]);
    	rt = Build(n, mid, last);
    	printf("Preorder:");
    	First(rt);
    	printf("\n");
    	return 0;
    }
    
    void First(BinTree *rt)
    {
    	if(rt)
    	{
    		printf(" %d", rt->Data);
    		First(rt->left);
    		First(rt->right);
    	}
    }
    
    BinTree * Build(int n, int *mid, int *last)
    {
    	BinTree *rt;
    	int i;
    	if(n <= 0)
    		return NULL;
    	rt = (BinTree *)malloc(sizeof(BinTree));
    	rt->Data = last[n-1];
    	rt->left = rt->right = NULL;
    	for(i = 0; i < n; i++)
    	{
    		if(mid[i] == rt->Data)
    			break;
    	}
    	rt->left = Build(i, mid, last);
    	rt->right = Build(n - i - 1, mid + i + 1, last + i);
    	return rt;
    }

以下为答案正确代码——非建树

#include <stdio.h>
    #include <string.h>
    
    void ans(int *post, int *in, int n)
    {
    	if(n <= 0)
    		return;
    	int root = post[n-1];
    	int i;
    	for(i = 0; i < n; i++)
    	{
    		if(in[i] == root)
    			break;
    	}
    	printf(" %d", root);
    	ans(post, in, i);
    	ans(post + i, in + i + 1, n - i - 1);
    }
    
    int main()
    {
    	int post[44], in[44];
    	int n, i;
    	scanf("%d", &n);
    	for(i = 0; i < n; i++)
    		scanf("%d", &post[i]);
    	for(i = 0; i < n; i++)
    		scanf("%d", &in[i]);
    	printf("Preorder:");
    	ans(post, in, n);
    	printf("\n");
    	return 0;
    }