题解 | 二叉树遍历

原本的先序遍历是不能确定一颗树树的，但其中的#号代表空树，因而可以唯一确定一颗二叉树，下面的代码比较简单，就是通过递归建树。

这道题的关键点就是 # 号代表空树。

#include <iostream>
#include <string>
using namespace std;

/*
	由先序遍历字符串建一颗二叉树，然后以中序遍历打印
*/

struct TreeNode {
	TreeNode* leftChild;
	TreeNode* rightChild;
	char c;
};

TreeNode* buildTree(TreeNode* &root, string preOrder, int& i) {

	TreeNode* curNode = new TreeNode;

	if (root == NULL)
	{
		root = curNode;
	}
	curNode->c = preOrder[i];
	i++;

	if (preOrder[i] != '#')
	{
		curNode->leftChild = buildTree(root, preOrder, i);
	}
	else {
		curNode->leftChild = NULL;
		i++;
	}
	if (preOrder[i] != '#')
	{
		curNode->rightChild = buildTree(root, preOrder, i);
	}
	else {
		curNode->rightChild = NULL;
		i++;
	}

	return curNode;
}
void printInorder(TreeNode* root) {
	if (root == NULL )
	{
		return;
	}
	printInorder(root->leftChild);
	cout << root->c << " ";
	printInorder(root->rightChild);

}
int main() {

	//abc##de#g##f###
	//# 表示空树
	string preOrder;

	cin >> preOrder;

	TreeNode* root = NULL;

	int i = 0;
	buildTree(root, preOrder, i);

	printInorder(root);

	return 0;
}