我看了一些博客，感觉还是自己写好。
序列化采用的moris前序遍历，反序列化也没使用递归。
说实话，反序列有些繁琐。我开始还在疑惑用栈做到底是否合适，但是有一想，别人用的递归也是压栈，我应该没问题。弹出栈的时候有问题，只有在第二次访问到该节点的才会弹出该节点，但是只靠栈自己是不可能知道的。再加额外复杂度，可以用数组或哈希，但是总感觉这样反倒更麻烦了，最后就封装了个新的类，栈中压的新类。至于new没有释放，这个没办法，leetcode就是这么设计的。

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

TreeNode* rightestNode1(TreeNode* root)
{
	TreeNode* node = root->left; 
	while(NULL!=node->right && root!=node->right)
		node = node->right;
	return node;
}

string serialize(TreeNode* root)
{
	string print = "";
	TreeNode* node = root;
	while(NULL != node)
	{
		if(NULL == node->left)
		{
			print += to_string(node->val);
			print += '_';
			print += "#_";
			node = node->right;
		}
		else
		{
			TreeNode* rightestNode = rightestNode1(node);
			if(NULL == rightestNode->right)
			{
				print += to_string(node->val);
				print += '_';
				rightestNode->right = node;
				node = node->left;
			}
			else
			{
				print += "#_";
				rightestNode->right = NULL;
				node = node->right;
			}
		}
	}
	print += "#_";
	return print;
}
TreeNode* deserialize(string data) {
	if('#' == data[0])
		return NULL;

	class booltree
	{
	public:
		TreeNode* node;
		bool left;
		bool right;
		booltree(TreeNode* _node, bool _left, bool _right):node(_node),left(_left),right(_right){};
	};

	stack<booltree>stacktree;
	while(1)
	{
		if('#' != data[0])
		{
			TreeNode* node = new TreeNode(atoi(data.c_str()));
			booltree boolnode = booltree(node, false,false);
			if(!stacktree.empty())
			{
				if(!stacktree.top().left)
				{
					stacktree.top().left = true;
					stacktree.top().node->left = node;
				}
				else
				{
					stacktree.top().right = true;
					stacktree.top().node->right = node;
				}
			}
			stacktree.push(boolnode);
		}
		else
		{
			if(!stacktree.top().left)
				stacktree.top().left = true;
			else
			{
				stacktree.top().right = true;
				do
				{
					if(1 == stacktree.size())
						return stacktree.top().node;
					stacktree.pop();
				}while(stacktree.top().left && stacktree.top().right);
			}
		}
		size_t pos = data.find_first_of("_");
		if(string::npos != pos)
			data = data.substr(pos + 1);
	}
}

string getSpace(int num)
{
    string space = " ";
    for (int i = 0; i < num; ++i)
    {
        space += " ";
    }
    return space;
}
void PrintInOrder(TreeNode *head, int height, string to, int len)
{
    if (NULL == head)
        return;
    PrintInOrder(head->right, height + 1, "v", len);
	string temp = to_string(head->val);
    string val = to + temp+ to;
    int lenM = val.length();
    int lenL = (len - lenM) / 2;
    int lenR = len - lenM - lenL;
    val = getSpace(lenL) + val + getSpace(lenR);
    cout << getSpace(height*len) << val << endl;
    PrintInOrder(head->left,height+1,"^",len);
}
void Print_TreeNode(TreeNode *head)
{
    cout << "Binary TreeNode : " << endl;
    PrintInOrder(head, 0, "H", 20);
    cout << endl;
}
void print(vector<int>a)
{
	for(int i=0;i<(int)a.size();++i)
		printf(",%d" + (int)(!i),a[i]);
	cout<<endl;
}

void print(string a)
{
	for(size_t i=0;i<a.length();++i)
		printf("%c",a[i]);
	cout<<endl;
}

int main(void)
{
//	TreeNode node1 = TreeNode(1);
//	TreeNode node2 = TreeNode(2);
//	TreeNode node3 = TreeNode(3);
//	TreeNode node4 = TreeNode(4);
//	TreeNode node6 = TreeNode(6);
//	TreeNode node7 = TreeNode(7);
//
//	node1.left = &node2;
//	node1.right = &node7;
//	node2.left = &node3;
//	node2.right = &node4;
//	node4.right = &node6;
	TreeNode nodea = TreeNode(4);
	TreeNode nodeb = TreeNode(-7);
	TreeNode nodec = TreeNode(-3);
	TreeNode noded = TreeNode(-9);
	TreeNode nodee = TreeNode(-3);
	TreeNode nodef = TreeNode(9);
	TreeNode nodeg = TreeNode(-7);
	TreeNode nodeh = TreeNode(-4);
	TreeNode nodei = TreeNode(6);
	TreeNode nodej = TreeNode(-6);
	TreeNode nodek = TreeNode(-6);
	TreeNode nodel = TreeNode(0);
	TreeNode nodem = TreeNode(6);
	TreeNode noden = TreeNode(5);
	TreeNode nodeo = TreeNode(9);
	TreeNode nodep = TreeNode(-1);
	TreeNode nodeq = TreeNode(-4);
	TreeNode noder = TreeNode(-2);

	nodea.left = &nodeb;
	nodea.right =& nodec;
	nodec.left = &noded;
	nodec.right = &nodee;
	noded.left = &nodef;
	noded.right = &nodeg;
	nodee.left = &nodeh;
	nodef.left = &nodei;
	nodeg.left = &nodej;
	nodeg.right = &nodek;
	nodei.left = &nodel;
	nodei.right = &nodem;
	nodej.left = &noden;
	nodek.left = &nodeo;
	nodel.right = &nodep;
	nodem.left = &nodeq;
	nodeo.right = &noder;

	string str = serialize(&nodea);
	print(str);
	Print_TreeNode(deserialize(str));
	return 0;
}