Pre order traversal. C++ iterative solution


  • 0
    W

    "n" denotes a null node. Normal Pre-order traversal. Currently beats > 80% submissions.

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            if(!root) return "n";
            string s = to_string(root->val) + ",";
            s += (serialize(root->left) + ",");
            s += serialize(root->right);
            return s;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            stack<TreeNode*> s;
            TreeNode* root = NULL;
            char* tok = strtok(const_cast<char*>(data.data()), ",");
            while (tok) {
                if (tok[0] == 'n') {
                    if (!s.empty()) {
                        if (!s.top()) {
                            s.pop(), s.pop();
                        }
                        else {
                            if (s.top()->left) {
                                s.pop();
                            }
                            else
                                s.push(nullptr);
                        }
                    }
                }
                else {
                    int v = atoi(tok);
                    auto node = new TreeNode(v);
                    if (!root) root = node;
                    if (!s.empty()) {
                        if (!s.top()) {
                            s.pop();
                            s.top()->right = node;
                            s.pop();
                        }
                        else {
                            if (s.top()->left) {
                                s.top()->right = node;
                                s.pop();
                            }
                            else
                                s.top()->left = node;
                        }
                    }
                    s.push(node);
                }
    
                tok = strtok(nullptr, ",");
            }
            return root;
        }
    };
    

Log in to reply
 

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