Binary Tree Serialization and Deserialization

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private static final String SEP = ",";
    private static final String NN = "X";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // StringBuilder res = new StringBuilder();
        // if(root == null){
        //     res.append(NN).append(SEP);
        // }else{
        //     res.append(root.val).append(SEP);
        //     res.append(serialize(root.left));
        //     res.append(serialize(root.right));
        // }
        // return res.toString();

        if(root == null) return NN;
        StringBuilder res = new StringBuilder();
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            if(root == null){
                res.append(NN).append(SEP);
                continue;
            }

            res.append(root.val).append(SEP);
            stack.push(root.right);
            stack.push(root.left);
        }
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split(SEP);
        if(data.equals(NN)) return null;
        Deque<String> queue = new LinkedList<>();
        queue.addAll(Arrays.asList(strs));
        // queue.addAll(Arrays.asList(data.split(SEP)));
        return buildTree(queue);
    }

    private TreeNode buildTree(Deque<String> nodes){
        String val = nodes.poll();
        if(val.equals(NN)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = buildTree(nodes);
        root.right = buildTree(nodes);
        return root;
    }
}

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

results matching ""

    No results matching ""