Force buckle 428 Serialize and deserialize n-tree DFS

428. Serialization and deserialization N Fork tree

Serialization is the process of converting a data structure into a sequence of bits , So you can store it in a file or in a memory buffer , So that the structure can be restored later in the same or different computer environment .

Design a serialization and deserialization N Fork tree algorithm . One N A fork tree means that each node has no more than N A rooted tree with child nodes . serialize / There are no restrictions on the algorithm implementation of deserialization algorithm . You just need to guarantee N The fork tree can be serialized into a string and the string can be deserialized into the original tree structure .

for example , You need to serialize the following  3- fork   Trees .

by  [1 [3[5 6] 2 4]]. You don't need to do it in this way , You can create and implement different methods yourself .

perhaps , You can follow LeetCode Sequence traversal serialization format , Each group of child nodes is separated by null values .

for example , The tree above can be serialized as  [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]

You do not have to follow the suggested format above , There are many different formats , So please be creative , Think of different ways to complete the problem .

Example 1:

 Input : root = [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]
 Output : [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]

Example 2:

 Input : root = [1,null,3,2,4,null,5,6]
 Output : [1,null,3,2,4,null,5,6]

Example 3:

 Input : root = []
 Output : []

Tips ：

• The range of the number of nodes in the tree is  [0, 104].
• 0 <= Node.val <= 104
• N The height of the fork tree is less than or equal to  1000
• Don't use class members / Global variables / Static variables to store state . Your serialization and deserialization algorithms should be stateless .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/serialize-and-deserialize-n-ary-tree
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

  

The result of doing the question

success ,DFS Straight through

Method ：DFS

My serial number format yes root ( Son )( Son )( Son ), Parentheses used , Mother before son

serialize ： root +(+ Recursive subtree serialization +)

Deserialization ：

1. Parse the part before the first left parenthesis , As root node

2. Use the stack to handle bracket pairs , The stack records the position of the left bracket , When you encounter a close bracket , Pop up stack , If the stack is empty , Indicates that the last pop-up bracket is in the outermost layer

3. Recursively resolve inner child nodes , Join the parent node

/*
// 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) {
         if(root == null) return "";
            StringBuilder sb = new StringBuilder();
            sb.append(root.val);
            if(root.children!=null){
                for(Node child:root.children){
                    sb.append("(");
                    sb.append(serialize(child));
                    sb.append(")");
                }
            }

            return sb.toString();
    }
	
    // Decodes your encoded data to tree.
    public Node deserialize(String data) {
        if(data.isEmpty()) return null;
            if(!data.contains("(")){
                Node d = new Node(Integer.parseInt(data));
                d.children = new ArrayList<>();
                return d;
            }
            Node root = new Node(Integer.parseInt(data.substring(0,data.indexOf("("))));
            root.children = new ArrayList<>();
            Stack<Integer> stack = new Stack<>();
            int n = data.length();
            for(int i = 0; i < n; i++){
                if(data.charAt(i)=='('){
                    stack.push(i);
                }else if(data.charAt(i)==')'){
                    int last = stack.pop();
                    if(stack.isEmpty()){
                        String part = data.substring(last+1,i);
                        root.children.add(deserialize(part));
                    }
                }
            }

        return root;
    }
}

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