恨登山临水
手寄七弦桐
目送归鸿
C++，创建二叉树。
看到这道题，一开始我想到的是利用中序+前/后序还原二叉树。后面写着写着觉得代码写太长了，这不符合剑指offer的风格，遂停下敲键盘的手，研究了以下普通前序的整数序列和这个字符串序列的区别，然后就发现了一个之前忽略的重要信息，那就是空结点！
为什么之前需要中序+前/后序才能确定一颗二叉树呢，因为这里说的前中后序序列都是整数序列，已经失去了空结点的信息，而如果我们能得到空结点信息，只需要一个序列就能确定一颗二叉树。
举个例子：
（灵魂画手）
我们如果遍历这棵树，生成的前序序列应该是：
1 2 4 3 5 6 7
但我们考虑空结点，假设空结点为-1，应该是：
1 2 4 -1 -1 -1 3 5 -1 -1 6 7 -1 -1 -1
然后用前序的思想去浏览这个序列的话，就会发现，完全可以再次用前序的过程建树。。。
比如前序递归走到了4，然后发现是-1，空结点，表示左子树为空，同理右子树也为空，遂回到上一层。。。
同样的思想，就能把整棵树给建立起来。
还有一个不得不说的点，9102年了，C++都要出20了，大家不要再手撸数字和字符串的转换了，亲测，std::string::stream非常好用！！！
具体代码如下：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
void preorder(TreeNode *root, string &str) {
stringstream ss;
if (!root) {
ss << -1;
str += " " + ss.str();
return ;
}
ss << root->val;
str += " " + ss.str();
preorder(root->left, str);
preorder(root->right, str);
}
char* Serialize(TreeNode *root) {
string str;
preorder(root, str);
char *sstr = new char[str.size()];
strcpy(sstr, str.c_str());
return sstr;
}
TreeNode *dfs(stringstream &ss) {
int value;
ss >> value;
if (value == -1) return nullptr;
TreeNode *root = new TreeNode(value);
root->left = dfs(ss);
root->right = dfs(ss);
return root;
}
TreeNode* Deserialize(char *str) {
stringstream ss;
ss << std::string(str);
return dfs(ss);
}
};
