A level order traversal solution


  • 0
    F

    Idea is pretty simple: traverse the tree using level order traversal to serialize the non-null nodes. If a null node is seen, serialize it as "N" but not add it into the queue anymore.

    Since all the leaf null nodes are offered into the queue once, I'm effectively ensuring that all non null nodes have exactly two children during deserialization.

    This solution is less space efficient comparing with DFS solutions as the queue uses O(n) space.

    public class Codec {

    public String serialize(TreeNode root) {
        if (root == null) return "N";
    
        StringBuilder tree = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                tree.append("N,");
            }
            else {
                tree.append(node.val).append(',');
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        tree.deleteCharAt(tree.length()-1);
        return tree.toString();
    }
    
    public TreeNode deserialize(String data) {
        String[] nodes = data.split("\\,");
        if (nodes.length == 1) return null;
        
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int i = 1;           // starting from the second node if root is not null
        
        while (i < nodes.length) {
            TreeNode node = queue.poll();
            
            String left = nodes[i++], right = nodes[i++];
            if (!left.equals("N")) {
                TreeNode lChild = new TreeNode(Integer.parseInt(left));
                node.left = lChild;
                queue.offer(lChild);
            }
            if (!right.equals("N")) {
                TreeNode rChild = new TreeNode(Integer.parseInt(right));
                node.right = rChild;
                queue.offer(rChild);
            }
        }
        return root;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.