Serialize And Deserialize A Given N Ary Tree 4,6/5 115 reviews
Design an algorithm to serialize and deserialize an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. It is needed to distinguish between two cases: 1. Complete n-ary Trees and 2. Sparse n-ary or non-Complete Trees. In the first case, assuming.
PermalinkJoin GitHub today
Asus p8h61 m lx lan drivers for mac pro. GitHub is home to over 50 million developers working together to host and review code, manage projects, and build software together.
Branch:master
Find file Copy path
Fetching contributors…
| /* |
| // Definition for a Node. |
| class Node { |
| public int val; |
| public List<Node> children; |
| public Node() {} |
| public Node(int _val,List<Node> _children) { |
| val = _val; |
| children = _children; |
| } |
| }; |
| */ |
| classCodec { |
| // Encodes a tree to a single string. |
| publicStringserialize(Noderoot) { |
| if (root null) { return''; } |
| StringBuilder sb =newStringBuilder(); |
| sb.append(root.val); |
| sb.append(','); |
| sb.append(root.children.size()); |
| sb.append('#'); |
| for (Node c: root.children) { |
| sb.append(serialize(c)); |
| } |
| return sb.toString(); |
| } |
| classRep { |
| Node n; |
| int end; |
| } |
| // Decodes your encoded data to tree. |
| publicNodedeserialize(Stringdata) { |
| if (data.length() 0) { returnnull; } |
| return parse(data, 0, data.length() -1).n; |
| } |
| privateRepparse(Stringdata, intstart, intend) { |
| if (start >= end) { returnnull; } |
| int comma = data.indexOf(',', start); |
| int split = data.indexOf('#', start); |
| int val =Integer.valueOf(data.substring(start, comma)); |
| int childNum =Integer.valueOf(data.substring(comma +1, split)); |
| Node n =newNode(); |
| n.val = val; |
| List<Node> children =newArrayList<>(); |
| int last = split; |
| for (int i =0; i < childNum; i++) { |
| Rep rep = parse(data, last +1, end); |
| last = rep.end; |
| children.add(rep.n); |
| } |
| n.children = children; |
| Rep r =newRep(); |
| r.n = n; |
| r.end = last; |
| return r; |
| } |
| } |
| // Your Codec object will be instantiated and called as such: |
| // Codec codec = new Codec(); |
| // codec.deserialize(codec.serialize(root)); |
Copy lines Copy permalink