【手把手带你刷好题】—— 42.清华大学考研复试题:二叉树遍历(牛客、较难)

【前言】

今天是刷题打卡第42天!

早成者未必有成,晚达者未必不达,一切都还来得及,加油鸭。

【手把手带你刷好题】—— 42.清华大学考研复试题:二叉树遍历(牛客、较难) 

原题:清华大学考研复试题:二叉树遍历

题目描述:

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。 

输入描述:

输入包括1行字符串,长度不超过100。

输出描述:

可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。 

题解:

【手把手带你刷好题】—— 42.清华大学考研复试题:二叉树遍历(牛客、较难)

如果只给出前序遍历肯定是不能构造一棵二叉树的,但是给出了空树部分就很简单啦。详情见代码哈。

代码执行:

#include<stdio.h>
#include<stdlib.h>

typedef struct TreeNode
{
	char val;
	struct TreeNode* left;
	struct TreeNode* right;
}TNode;

TNode* CreateTree(char* a, int* pi)
{
	if (a[*pi] == '#')//空树不需要递归构建,但是需要i++
	{
		(*pi)++;
		return NULL;
	}
	//不是空树就需要递归构建树
	TNode* root = (TNode*)malloc(sizeof(TNode));
	if (root == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		root->val = a[*pi];//将当前数组中的值作为根节点值
		(*pi)++;
		root->left = CreateTree(a, pi);//递归构建左子树
		root->right = CreateTree(a, pi);//递归构建右子树
		return root;
	}
}

void InOrder(TNode* root)//中序递归遍历
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%c ", root->val);
	InOrder(root->right);
}

int main()
{
	char arr[30] = { 0 };
	gets(arr);
	int i = 0;
	TNode* root = CreateTree(arr, &i);
	InOrder(root);
	return 0;
}

结语

今天是刷题打卡第42天!

加油吧少年。

【手把手带你刷好题】—— 42.清华大学考研复试题:二叉树遍历(牛客、较难)

上一篇:Spring data jpa讲讲它的常用CRUD类,Sort的使用和PageRequest,还有JpaSpecificationExecutor!


下一篇:二叉树遍历