/*
// 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:
// Encodes a tree to a single string.
string serialize(Node* root) {
}
// Decodes your encoded data to tree.
Node* deserialize(string data) {
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children
"""
class Codec:
def serialize(self, root: 'Node') -> str:
"""Encodes a tree to a single string.
:type root: Node
:rtype: str
"""
from collections import deque
if not root: return ""
queue = deque([root])
res = []
while queue:
node = queue.pop()
res.append(str(node.val))
res.append(str(len(node.children)))
for ch in node.children:
queue.appendleft(ch)
return ",".join(res)
def deserialize(self, data: str) -> 'Node':
"""Decodes your encoded data to tree.
:type data: str
:rtype: Node
"""
# print(data)
from collections import deque
if not data: return
data = iter(data.split(","))
root = Node(int(next(data)), [])
queue = deque([[root, int(next(data))]])
while queue:
node, num = queue.pop()
for _ in range(num):
tmp = int(next(data))
tmp_num = int(next(data))
tmp_node = Node(tmp, [])
node.children.append(tmp_node)
queue.appendleft([tmp_node, tmp_num])
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children
"""
class Codec:
def serialize(self, root: 'Node') -> str:
"""Encodes a tree to a single string.
:type root: Node
:rtype: str
"""
res = []
def dfs(root):
if not root: return
res.append(str(root.val))
res.append(str(len(root.children)))
for ch in root.children:
dfs(ch)
dfs(root)
# print(res)
return ",".join(res)
def deserialize(self, data: str) -> 'Node':
"""Decodes your encoded data to tree.
:type data: str
:rtype: Node
"""
if not data: return
data = iter(data.split(","))
def dfs():
root = Node(int(next(data)), [])
num = int(next(data))
for _ in range(num):
root.children.append(dfs())
return root
return dfs()
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
/*
// 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:
// Encodes a tree to a single string.
string serialize(Node* root) {
if (root == NULL)
return "";
string res = to_string(root->val) + "[";
for (auto node : root->children) {
res += serialize(node) + ",";
}
if (res.back() == ',')
res.pop_back();
res += "]";
return res;
}
// Decodes your encoded data to tree.
Node* deserialize(string data) {
cout << data << endl;
string value;
Node* head = NULL;
stack<Node*> s;
for (int i = 0; i < data.size(); ++i) {
const char& c = data[i];
if ((c >= '0' && c <= '9') || c == '+' || c == '-') {
value += c;
} else if (c == '[') {
Node* node = new Node(stoi(value));
if (head == NULL)
head = node;
s.push(node);
value.clear();
} else if (c == ']') {
Node* node = s.top();
s.pop();
if (!s.empty()) {
Node* prev_node = s.top();
prev_node->children.push_back(node);
}
}
}
return head;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Codec {
// Encodes a tree to a single string.
public String serialize(Node root) {
StringBuilder sb = new StringBuilder();
if (root == null) {
return sb.toString();
}
encode(root, sb);
return sb.toString();
}
private void encode(Node node, StringBuilder sb) {
if (node == null) {
return;
}
sb.append(node.val);
sb.append(" ");
boolean hasChildren = !node.children.isEmpty();
// only append "[ ]" when the node has children
if (hasChildren) {
sb.append("[ ");
}
for (int i = 0; i < node.children.size(); i++) {
Node children = node.children.get(i);
encode(children, sb);
if (i == node.children.size() - 1) {
sb.deleteCharAt(sb.length() - 1);
}
}
if (hasChildren) {
sb.append(" ] ");
}
}
// Decodes your encoded data to tree.
public Node deserialize(String data) {
if (data.isEmpty()) {
return null;
}
String[] strings = data.split(" ");
Stack<Node> stack = new Stack<Node>();
Node root = null;
Node cur = null;
for (String s : strings) {
if (s.equals("[")) {
stack.push(cur);
} else if (s.equals("]")) {
stack.pop();
} else {
Node node = new Node(Integer.valueOf(s));
node.children = new LinkedList<Node>();
if (root == null) {
root = node;
} else {
Node parent = stack.peek();
parent.children.add(node);
}
cur = node;
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
