Iterative solution using Queue (C++) same as leetcode


  • 0
    F

    The idea is level order traversal:

    1. Serialize: First, add root to the queue. Then, for each node, append its value to the result string, and then add its left and right children to queue. If the node is NULL, simply skip to the next node. Loop until the queue is empty.
      Notice that this will result some NULLs at the end of the result, which is ok. Just erase all these NULLs before return.
    2. Deserialize: This time I'm using two queues. First, convert the serialized data to the data queue. Second, add root to the Node queue; then, for each node popped from the Node queue, I also pop two values from the data queue (if not empty); if the first data is real data, create the current node's left child and push it to the Node queue; do the same thing for the second data; loop until the data queue is empty.

    C++:

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            queue<TreeNode *> q;
            string s;
            if (root) q.push(root);
            while (!q.empty()) {
                TreeNode *n = q.front();
                q.pop();
                if (n) {
                    q.push(n->left);
                    q.push(n->right);
                    s += to_string(n->val) + ",";
                } else {
                    s += "n,";
                }
            }
            if (s.length()) s.erase(s.find_last_not_of("n,")+1);
            return s;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            if (data.empty()) return NULL;
            queue<string> qData;
            int i = 0, j;
            do {
                j = data.find(',', i);
                if (j != string::npos) qData.push(data.substr(i, j-i));
                else qData.push(data.substr(i));
                i = j+1;
            } while (j != string::npos);
            
            queue<TreeNode *> qNodes;
            TreeNode *root = new TreeNode(stoi(qData.front()));
            TreeNode *curr = NULL;
            qNodes.push(root);
            qData.pop();
            while (!qData.empty()) {
                string val1 = "", val2 = "";
                val1 = qData.front();
                qData.pop();
                if (!qData.empty()) {
                    val2 = qData.front();
                    qData.pop();
                }
                curr = qNodes.front();
                qNodes.pop();
                if (val1 != "" && val1 != "n") {
                    curr->left = new TreeNode(stoi(val1));
                    qNodes.push(curr->left);
                }
                if (val2 != "" && val2 != "n") {
                    curr->right = new TreeNode(stoi(val2));
                    qNodes.push(curr->right);
                }
            }
            return root;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.