Serialize & Deserialize A Tree

来源：EPI, Facebook Interview

原帖：http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html

题目：
A very frequent interview question. Suppose you have a tree, how could you serialize it to file and revert it back? For example,
         1
      /    \
     2      3
      \     /  
       4   5  
      /  \
     6    7

[Thoughts]
一个比较简单直接的做法是，通过前序遍历来做，把所有空节点当做“#”来标示。那么这棵树可以表示为
             1
          /     \
         2        3
       /   \     /   \
     #      4    5     #
          /   \
         6     7
        /  \  /  \
       #   # #    #
那么前序遍历的结果就是： {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'}; 代码如下：
参考 http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html

代码：

 // Tree serialize   
 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 void serialize(TreeNode* root, vector<char> &result) {  
   if (root == NULL) {  
     result.push_back('#'); // 表示终结结点  
     return;  
   }  
   result.push_back(root->val + '0');  
   serialize(root->left, result);  
   serialize(root->right, result);  
 }  
   
 // de-serialize  
 TreeNode* deserialize(const vector<char> &num, int &index) {  
   if (index >= num.size()) {  
    return NULL;  
   }   
   if (num[index] == '#') {  
     index++;  
     return NULL;  
   }  
   TreeNode *root = new TreeNode(num[index] -'0');  
   index++;  
   root->left = Deserialize(num, index);  
   root->right = Deserialize(num, index);  
   return root;  
 }  
   
 int main() {  
   vector<char> numbers = {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'};  
   int index = 0;  
   TreeNode* root = deserialize(number, index);  
   vector<char> res;  
   serialize(root, res);  
   return 0;  
 }  

Deserialize Tree的stack解法
EPI 6.8. pg. 236.
Reconstructing A Binary Tree From A Preorder Traversal With Marker. Design an O(n) time algorithm for reconstructing a binary tree from a preorder visit sequence that uses null to mark empty children. How would you modify your reconstruction algorithm if the sequence corresponded to a postorder or inorder walk.

代码：

 #define null 0;  
 TreeNode* reconstruct_preorder(const vector<int>& preorder) {  
   stack<TreeNode*> s;  
   // traversal back to forth  
   for (auto it = preorder.crbegin(); it != preorder.crend(); ++it) {  
     if (!(*it)) {  
       s.push(NULL);  
     } else {  
       TreeNode* l = s.top(); s.pop();  
       TreeNode* r = s.top(); s.pop();  
       TreeNode* root = new TreeNode(*it);  
       root->left = l;  
       root->right = r;  
       s.push(root);  
     }  
   }   
   return s.top();  
 }