297. Serialize and Deserialize Binary Tree二叉树的序列化和反序列化（就用Q）

［抄题］：

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example:

You may serialize the following tree:

    1

   / \

  2   3

     / \

    4   5

as "[1,2,3,null,null,4,5]"

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

不知道空节点怎么处理：随便用一个什么字符串代替就行了，反正压缩之后也看不见

［英文数据结构或算法，为什么不用别的数据结构或算法］：

pre-order，写着方便

用deque，先都存了，然后全部先进先出

［一句话思路］：

把空节点提前定义为一个特殊的字符串来处理

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

需要提前定义 spliter = ","

［画图］：

［一刷］：

节点为空和新建树是两个独立的过程，需要用if else隔开
反序列化只需要用q做参数即可，因为节点都是recursion中新建的

［二刷］：

节点为空就是root本身 == null, 不是root.val == null
写公式就完成recursion了，此时可以return

［三刷］：

字符串判断相等应该用equals

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

光有死记硬背不行，一点不背想凭空写更是无稽之谈

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［算法思想：递归/分治/贪心］：递归

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

271. Encode and Decode Strings就是用stringbuilder就行了

449. Serialize and Deserialize BST 不能中序，因为对递增有要求，输入串未必满足

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Codec {

    //ini: split, null

    private static final String split = ",";

    private static final String NN = " ";

    // Encodes a tree to a single string.

    public String serialize(TreeNode root) {

        //new StringBuilder

        StringBuilder sb = new StringBuilder();

        //

        buildString(root, sb);

        return sb.toString();

    }

    private void buildString(TreeNode root, StringBuilder sb) {

        //if null, else preorder

        if (root == null) {

            sb.append(NN).append(split);

        }else {

            sb.append(root.val).append(split);

            buildString(root.left, sb);

            buildString(root.right, sb);

        }

    }

    // Decodes your encoded data to tree.

    public TreeNode deserialize(String data) {

        //ini: deque

        Deque<String> queue = new LinkedList<>();

        //put into queue

        queue.addAll(Arrays.asList(data.split(",")));

        return buildTree(queue);

    }

    private TreeNode buildTree(Deque<String> queue) {

        String val = queue.remove();

        //if null

        if (val.equals(NN)) {

            return null;

        }else {

            //else: preoder, return

            TreeNode node = new TreeNode(Integer.valueOf(val));

            node.left = buildTree(queue);

            node.right = buildTree(queue);

            return node;

        }

    }

}

// Your Codec object will be instantiated and called as such:

// Codec codec = new Codec();

// codec.deserialize(codec.serialize(root));

巴特西

297. Serialize and Deserialize Binary Tree二叉树的序列化和反序列化（就用Q）

最新文章

热门文章