序列化二叉树

题目

请实现两个函数,分别用来序列化和反序列化二叉树

解题思路

  1. 通过前序遍历,进行序列化和反序列化
  2. 对于空节点用 $ 来代替

    String Serialize(TreeNode root) {
    if (root==null) return "";
    
    LinkedList<String> res = new LinkedList<>();
    
    serialize(res, root);
    
    StringBuilder builder = new StringBuilder();
    res.forEach(v-> builder.append(v).append(","));
    
    return builder.toString();
    }
    
    
    private void serialize(LinkedList<String> res, TreeNode root) {
    if (root == null) {
        res.addLast("$");
        return;
    }
    
    res.addLast(String.valueOf(root.val));
    serialize(res, root.left);
    serialize(res, root.right);
    }
    
    TreeNode Deserialize(String str) {
    if (str == null || str.length() == 0) return null;
    
    return deserialize(str.split(","), new int[]{0});
    }
    
    
    private TreeNode deserialize(String[] str, int[] index) {
    if (index[0] >= str.length) return null;
    
    String c = str[index[0]++];
    if (c.equals("$")) return null;
    
    TreeNode node = new TreeNode(Integer.valueOf(c));
    node.left = deserialize(str, index);
    node.right = deserialize(str, index);
    
    return node;
    }