297. Serialize and Deserialize Binary Tree (Hard)

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

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]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solutions

class Codec {

    // The most crucial stuff is how we define the visiting path, here we will take a
    // simple string as an example to demonstrate. For node N, the path expression is
    // "lllr", which denotes the sequence of nodes we take and it can be interpreted as
    // step 1. move left; step 2. move left; step 3. move left; step 4. move right.

    // Solution A

    // 1. Sort the max depth of tree n.
    // 2. Define an array (2^n)-1 initialized with null
    // 3. Recurse the tree nodes and work out the corresponding index of each node
    // in above array in light of the path, then set the node value

    // Solution B

    // 1. Define a List which is used to keep the unique path toward specific node.
    // 2. Recurse the tree nodes and combine the visiting path and node value, then store
    // it to above List. The combination looks like "llr=n", where l and r are
    // direction of branch; represents the link between two nodes; = signifies the separator
    // between path and node value.

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }

        List<String> nodePaths = new ArrayList<>();

        recurse(root, "", nodePaths);

        String ans = "";
        for (String path : nodePaths) {
            ans += path + " ";
        }

        return ans.trim();
    }

    private void recurse(TreeNode node, String path, List<String> nodePaths) {
        if (node == null) {
            return;
        }

        // remove prefix '>'
        nodePaths.add(path + "#" + node.val);

        recurse(node.left, path + "l", nodePaths);

        recurse(node.right, path + "r", nodePaths);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        TreeNode root = null;

        String[] nodeStrs = data.split(" ");
        for (String str : nodeStrs) {
            String path = str.split("#")[0];
            int val = Integer.valueOf(str.split("#")[1]);

            if (path == null || path.length() == 0) {
                root = new TreeNode(val);

                continue;
            }

            TreeNode tmp = root;
            for (int i = 0; i < path.length(); i++) {
                int c = path.charAt(i);

                if (i == path.length() - 1) {
                    if (c == 'l') {
                        tmp.left = new TreeNode(val);
                    } else {
                        tmp.right = new TreeNode(val);
                    }

                    break;
                }

                if (path.charAt(i) == 'l') {
                    tmp = tmp.left;
                } else {
                    tmp = tmp.right;
                }
            }
        }

        return root;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""