---
tags: leetcode
---

# [297. Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ 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:
    string serialize(TreeNode *root) {
        if (root == nullptr) {
            return "";
        }

        stringstream output;

        serialize(root, output);
        return output.str();
    }

    TreeNode *deserialize(string data) {
        if (data.empty()) {
            return nullptr;
        }

        stringstream input(data);
        return deserialize(input);
    }

private:
    void serialize(TreeNode *root, stringstream &output) {
        if (root == nullptr) {
            output << "x ";
            return;
        }

        output << to_string(root->val) << " "; 
        serialize(root->left, output);
        serialize(root->right, output);
    }

    TreeNode *deserialize(stringstream &input) {
        string value;

        input >> value;
        if (value == "x") {
            return nullptr;
        }

        TreeNode *node = new TreeNode(static_cast<int>(strtol(value.c_str(), NULL, 10)));
        node->left = deserialize(input);
        node->right = deserialize(input);

        return node;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

## Time Complexity
$O(n)$
$n$ is the number of nodes in the binary tree referred by `root`.
## Space Complexity
$O(H)$
$H$ is the height of the binary tree referred by `root`.
# Miscellaneous
<!--
# Test Cases

[1,2,3,null,null,4,5]

[]

[1]

[1,2]

[1,2,null,3,null,4,null,5]

-->