c++版本先序遍历功能实现

#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

//递归打印后序遍历
void lastOrderRecur(TreeNode* head)
{
	if (head == nullptr)
		return;
	lastOrderRecur(head->left);
	lastOrderRecur(head->right);
	cout << head->val << ", ";
}


//按照节点后序遍历进行序列化成一个字符串
string serialByLastOrder(TreeNode* head)
{
	//如果是空节点就序列化成#!
	if (head == nullptr)
	{
		return "#!";
	}
	string res = serialByLastOrder(head->left);
	res = res + serialByLastOrder(head->right);
	res = res + std::to_string(head->val) + "!";
	return res;
}

//按照一个字符串数组构造出一棵树并返回这棵树的根节点
//关键就在于这个引用就地改变
TreeNode* deserialByLastHelp(vector<int>& vec)
{
	int value = vec.back();
	vec.pop_back();
	if (value == -1)
		return nullptr;
	TreeNode* node = new TreeNode(value);
	node->right = deserialByLastHelp(vec);
	node->left = deserialByLastHelp(vec);
	return node;
}

//123！#！
TreeNode* deserialByLastOrder(char* str)
{
	vector<int> vec;
	//考察到字符串的反向遍历
	//首先要把str这个字符串转化成一个vector<int>数组，因为字符串不好从后面遍历
	//首先判断一下这是不是一棵空树
	if (str == nullptr)
		return nullptr;
	while(*str)
	{
		while (*str == ‘#‘)
		{
			//如果是空节点干脆就存-1进去，避免和0冲突了
			vec.push_back(-1);
			str++; str++;
		}
		int val = 0;
		while (*str != ‘!‘)
		{
			val = 10 * val + (*str - ‘0‘);
			str++;
		}
		vec.push_back(val);
		str++;//同时要跳过那个！
	}
	cout << "vec see:";
	for (auto start = vec.begin(); start != vec.end(); start++)
	{
		cout << *start << ",";
	}
	return deserialByLastHelp(vec);
}


int main()
{
	TreeNode* head = new TreeNode(5);
	head->left = new TreeNode(3);
	head->right = new TreeNode(8);
	head->left->left = new TreeNode(1);
	head->left->right = new TreeNode(2);
	head->right->left = new TreeNode(4);
	head->right->right = new TreeNode(5);
	head->right->left->left = new TreeNode(6);
	head->right->right->left = new TreeNode(9);
	head->right->right->right = new TreeNode(11);
	
	cout << "last-order:";
	lastOrderRecur(head);
	cout << "\nserial binary:";
	string res = serialByLastOrder(head);
	cout << res << endl;
	char* s_char = (char*)res.c_str();//从string转换到char*
	TreeNode* dehead = deserialByLastOrder(s_char);
	cout << "\ndeserial binary:";
	lastOrderRecur(dehead);
	
	return 0;
}