---
tags: leetcode
---

# [428. Serialize and Deserialize N-ary Tree](https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Codec {
public:
    string serialize(Node *root) {
        if (root == nullptr) {
            return "";    
        }

        stringstream output;
        
        serialize(root, output);
        cout << output.str() << endl;
        return output.str();
    }
    
    Node *deserialize(string data) {
        if (data.empty()) {
            return nullptr;
        }
        
        stringstream input(data);
        return deserialize(input);
    }

private:
    void serialize(Node *root, stringstream &output) {
        if (root == nullptr) {
            output << "x ";
            return;
        }
        
        output << to_string(root->val) << " " << to_string(root->children.size()) << " ";
        for (Node *child : root->children) {
            serialize(child, output);
        }
    }
    
    Node *deserialize(stringstream &input) {
        string value;
        
        input >> value;
        if (value == "x") {
            return nullptr;
        }
        
        int nodeValue = static_cast<int>(strtol(value.c_str(), NULL, 10));
        Node *node = new Node(nodeValue);
        
        input >> value;
        int numChildren = static_cast<int>(strtol(value.c_str(), NULL, 10));
        for (int i = 0; i < numChildren; ++i) {
            node->children.push_back(deserialize(input));
        }
        
        return node;
    }
};

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

## Time Complexity
$O(n)$
$n$ is the number of nodes in the n-ary tree.
## Space Complexity
$O(H)$
$H$ is the height of the n-ary tree.
# Miscellane
<!--
# Test Cases

[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

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

[]

-->