Simple O(n) solution to keep track of number of nodes traversed during deserialization


  • 0
    V

    When deserializing you need to keep track how many nodes/indexes you traversed on left subtree, so you can correct start the index for right subtree.

    public class Codec {
        char sep = ',';
        
        private class NodeAndCount {
            public TreeNode node;
            public int count;
            NodeAndCount(TreeNode node, int count) {
                this.node = node;
                this.count = count;
            }
        }
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root==null)
                return new String("NULL");
            return String.valueOf(root.val) + sep + serialize(root.left) + sep + serialize(root.right);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data==null) return null;
            String[] newData = data.split(",");
            NodeAndCount nodeAndCount =  deserializeUtil(newData,0,newData.length-1,0);   
            return nodeAndCount.node;
        }
        
        NodeAndCount deserializeUtil(String[] data, int start, int end, int count) {
            if(data[start].equals("NULL") ){
                return new NodeAndCount(null,1);
            }
            
            TreeNode n = new TreeNode(Integer.parseInt(data[start]));
            NodeAndCount left = deserializeUtil(data, start+1, end, 0);
            n.left= left.node;
            NodeAndCount right = deserializeUtil(data, start+1+left.count,end, 0);
            n.right = right.node;
            
            return new NodeAndCount(n,left.count + right.count+1);
        }
    }
    

Log in to reply
 

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