267. Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

实现序列化和反序列化二叉树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s;
        dfs(root, s);
        return s;
    }
    
    void dfs(TreeNode *cur, string &s) {
        if (cur == NULL) {
            s += "#";
            return;
        }
        s += to_string(cur->val) + ",";
        dfs(cur->left, s);
        dfs(cur->right, s);
    }
    
    TreeNode* dfs(string &s, int &pos) {
        string num;
        for (; pos < s.length(); ++pos) {
            if (s[pos] == '#') {
                ++pos;
                return NULL;
            }
            if (s[pos] == ',') break;
            num += s[pos];
        }
        ++pos;
        TreeNode *cur = new TreeNode(stoi(num));
        cur->left = dfs(s, pos);
        cur->right = dfs(s, pos);
        return cur;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int pos = 0;
        return dfs(data, pos);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

1. bfs遍历树，每个节点的值接连存在string里，再接一个"/"隔开

2. 即使是null节点用特殊符号比如#存下来

3. deserilize时先用"/"拿到所有用str表示的node. 然后初始化第一个TreeNode, 继续bfs遍历。 只是这次循环判断条件不再是q.empty()；而是节点数目是否小于node.size。queue.pop()每次出来的就是parent. 后面两个分别就是它的左右子节点，如果是# 就跳过该子节点。

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        if (root == NULL) return res;
        queue<TreeNode *> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                const auto node = q.front();
                q.pop();
                if (!node) {
                    res += "#/";
                } else {
                    res += to_string(node->val) + "/";
                    q.push(node->left);
                    q.push(node->right);
                }               
            }
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return NULL;
        const char SPLITER = '/';
        const string NONE = "#";
        vector<string> nodes = split(data, SPLITER);
        auto it = nodes.begin();
        TreeNode *root = new TreeNode(stoi(*(it++)));
        queue<TreeNode *> q;
        q.push(root);
        while (it != nodes.end()) {
            const auto p = q.front();
            q.pop();
           // cout << *it << ":" <<i++ <<endl;
            if (*it != NONE) {
                p->left = new TreeNode(stoi(*it));
                q.push(p->left);
            } 

            if (*(++it) != NONE) {
                p->right = new TreeNode(stoi(*it));
                q.push(p->right);
            }
            ++it;
        }
        return root;
    }

private:    
    vector<string> split(string str, char delimiter) {
        vector<string> result;
        int last = 0;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == delimiter) {
                result.push_back(str.substr(last, i - last));
                last = i + 1;
            }
        }
        cout << str.size() << endl;
        return result;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

 /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private static final String SPLITER = "/";
    private static final String NONE = "#"; 

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node == null) {
                    sb.append(NONE).append(SPLITER);
                } else {
                    sb.append(node.val).append(SPLITER);
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
            }
        }

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] vals = data.split(SPLITER);
        if (vals.length == 0 || vals[0].equals(NONE)) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        queue.offer(root);
        for (int i = 1; i < vals.length; i++) {
            TreeNode parent = queue.poll();
            if (!vals[i].equals(NONE)) {
                parent.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(parent.left);
            }
            if (!vals[++i].equals(NONE)) {
                parent.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(parent.right);
            }           
        }

        return root;
    }  
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Analysis

时间复杂度O(N).