297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

S: level order traversal + queue

因为TreeNode只包含int， 可用#分割不同node，用@标记null child

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string result = "";
        if (!root) return result;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            result += '#';
            if (node) {
                result += to_string(node->val);
                q.push(node->left);
                q.push(node->right);
            } else {
                result += '@';
            }
        }
        return result;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.size() < 2) {
            return NULL;
        }
        int idx = 0;
        TreeNode* root = makeNode(data, idx);
        queue<TreeNode*> q;
        q.push(root);
        while (idx < data.size()) {
            TreeNode* node = q.front();
            q.pop();
            node->left = makeNode(data,idx);
            node->right = makeNode(data, idx);
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
        return root;
    }

private:
    TreeNode* makeNode(string& data, int& idx) {
        idx++;
        if (idx >= data.size()) {
            return NULL;
        }
        if (data[idx] == '@') {
           idx++;
           return NULL;
        } else {
            string s = "";
            while (idx < data.size() && data[idx] != '#') {
                s += data[idx];
                idx++;
            }
            TreeNode* node = new TreeNode(stoi(s));
            return node;
        }

    }
};

331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as#.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string"9,3,4,#,#,1,#,#,2,#,6,#,#", where#represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character'#'representingnullpointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as"1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Returntrue

Example 2:
"1,#"
Returnfalse

Example 3:
"9,#,#,1"
Returnfalse

S1: count indegree & outdegree

每个节点（除了root）都有一个indegree （parent）

非null节点有2个outdegree（children），null节点有0个outdegree。count degree看看最后是否为0。

注意中途degree不可大于0，若大于0说明有多余的null节点

    bool isValidSerialization(string preorder) {
        if (preorder.size() == 0) return true;
        int degree = -1,  idx = 0;
        while (idx < preorder.size()) {
            string cur = getNext(preorder, idx);
            degree++;  //every node has 1 in degree;
            if (degree > 0) return false;  //has extra null node
            if (cur != "#") degree -= 2;  //none-null node has 2 out degree;     

        }
        return degree == 0;
    }

    string getNext(string s, int& i) {
        int j = min(s.find(',', i), s.size());      
        string result = s.substr(i, j - i);
        i = j + 1;
        return result;
    }

S2：dfs traversal

判断左右子树是否valid，以及有没有多余的node

    bool isValidSerialization(string preorder) {
        int idx = 0;
        return dfs(preorder, idx) && idx >= preorder.size();
    }

    bool dfs(string preorder, int& idx) {
        if (idx >= preorder.size()) return false;
        int j = preorder.find(',', idx);
        if (j == string::npos) j = preorder.size();
        string cur = preorder.substr(idx, j - idx);
        idx = j + 1;
        if (cur == "#") return true;
        return dfs(preorder, idx) && dfs(preorder, idx);
    }