C++ level order iterative solution


  • 0
    M
    /**
     * 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 {
    private:
        void split (vector<string>& v, string s, char delim) {
            if (s.length() == 0) {
                return;
            }
            auto i = 0;
            auto pos = s.find(delim);
            while (pos != string::npos) {
                v.push_back(s.substr(i, pos-i));
                i = ++pos;
                pos = s.find(delim, pos);
            }
            if (pos == string::npos)
                v.push_back(s.substr(i, s.length()));
        }
    public:
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            string s = "";
            if (!root) {
                return s;
            }
            queue<TreeNode*> treeq;
            treeq.push(root);
            int curlevel = 1, nextlevel = 0;
            TreeNode* cur = NULL;
            vector<string> result;
            while (!treeq.empty()) {
                for (int i = 0; i < curlevel; i++) {
                    cur = treeq.front();
                    treeq.pop();
                    result.push_back(cur ? to_string(cur->val) : "null");
                    if (cur) {
                        treeq.push(cur->left);
                        treeq.push(cur->right);
                        nextlevel += 2;
                    }
                }
                curlevel = nextlevel;
                nextlevel = 0;
            }
            while (result.back() == "null") {
                result.pop_back();
            }
            
            for (auto r : result) {
                s += r + ",";
            }
            s.pop_back();
            return s;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            vector<string> tree;
            split(tree, data, ',');
            if (tree.size() == 0) {
                return NULL;
            }
            int left = 0, right = 1;
            queue<TreeNode*> treeq;
            TreeNode* root = new TreeNode(stoi(tree[0]));
            treeq.push(root);
            TreeNode* cur = NULL;
            while (right < tree.size()) {
                int stop = right;
                while (left < stop) {
                    if (tree[left] != "null") {
                        cur = treeq.front();
                        treeq.pop();
                        TreeNode* lc = (tree[right] == "null") ? NULL : new TreeNode(stoi(tree[right]));
                        cur->left = lc;
                        treeq.push(lc);
                        right++;
                        if (right == tree.size()) {
                            break;
                        }
                        TreeNode* rc = (tree[right] == "null") ? NULL : new TreeNode(stoi(tree[right]));
                        cur->right = rc;
                        treeq.push(rc);
                        right++;
                        if (right == tree.size()) {
                            break;
                        }
                    } else {
                        treeq.pop();
                    }
                    left++;
                }
            }
            return root;
        }
    };
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.deserialize(codec.serialize(root));
    
    
    

Log in to reply
 

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