力扣 428. 序列化和反序列化 N 叉树 DFS

428. 序列化和反序列化 N 叉树

序列化是指将一个数据结构转化为位序列的过程，因此可以将其存储在文件中或内存缓冲区中，以便稍后在相同或不同的计算机环境中恢复结构。

设计一个序列化和反序列化 N 叉树的算法。一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。序列化 / 反序列化算法的算法实现没有限制。你只需要保证 N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。

例如，你需要序列化下面的 3-叉 树。

为 [1 [3[5 6] 2 4]]。你不需要以这种形式完成，你可以自己创造和实现不同的方法。

或者，您可以遵循 LeetCode 的层序遍历序列化格式，其中每组孩子节点由空值分隔。

例如，上面的树可以序列化为 [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:

输入: 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]
输出: [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]

示例 2:

输入: root = [1,null,3,2,4,null,5,6]
输出: [1,null,3,2,4,null,5,6]

示例 3:

输入: root = []
输出: []

提示：

• 树中节点数目的范围是 [0, 104].
• 0 <= Node.val <= 104
• N 叉树的高度小于等于 1000
• 不要使用类成员 / 全局变量 / 静态变量来存储状态。你的序列化和反序列化算法应是无状态的。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/serialize-and-deserialize-n-ary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  

做题结果

成功，DFS直接过

方法：DFS

我的序列号格式 是 根(子)(子)(子)，用的括号，先母后子即可

序列化：根+(+递归子树序列化+)

反序列化：

1. 解析第一个左括号前的部分，作为根节点

2. 使用栈来处理括号对，栈记录左括号的位置，当遇到右括号时，弹出栈，如果栈空，说明最后一个弹出的括号在最外层

3. 递归解析内层子节点，加入父节点

/*
// 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));