NowCoder刷题(1)【树】二叉树的遍历

二叉树的遍历(IO型)

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

题目描述

如图所示的这棵树

前序输出结果为

A-B-D-#-#-E-#-#-C-#-#

还原过程

示例1

示例2

——前序遍历还原

代码实现：

#include<stdio.h>
//定义一棵树的结构
typedef struct TreeNode
{
	struct TreeNode* left;
	struct TreeNode* right;
	char val;
}TreeNode;
//根据前序遍历还原这棵树
TreeNode* CreatBackTree(char* a, int* i)
{
	if (a[*i] == '#')
	{
		//井号说明该结点为空
		++(*i);
        return NULL;
	}
	TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
	if (root == NULL)
	{
		printf("malloc is fail");
		exit(-1);
	}
	root->val = a[*i];
	(*i)++;
	root->left = CreatBackTree(a, i);//构建子树的时候还是从这个结点开始
	root->right = CreatBackTree(a, i);
	return root;
} 
//中序遍历
void InOrderTree(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrderTree(root->left);
	printf("%c ", root->val);
	InOrderTree(root->right);
}
int main(void)
{
	//输入一个字符数组
	char arry[100];
	scanf("%s", arry);//输入字符串不用取地址符
	int i = 0;
	TreeNode* root = CreatBackTree(arry, &i);
	InOrderTree(root);
	return 0;
}