Iterative Solution - The Most Compact Serialization Possible (No Additional Chars)


  • 0
    R

    Serialization is simply breadth-first traversal of the elements separated by comma.
    No additional chars, markers, etc. are used, hence it's the most compact way possible.

    Deserialization starts scanning from the beginning and assigns left/right children if they fit the BST criteria, and skips the ones that don't meet the criteria. The decision is made by keeping track of each node's upper-lower bounds, which they inherit from their parents.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left;
     *     public TreeNode right;
     *     public TreeNode(int x) { val = x; }
     * }
     */
    public class Codec 
    {
        Dictionary<TreeNode,int> upperBound = new Dictionary<TreeNode,int>();
        Dictionary<TreeNode,int> lowerBound = new Dictionary<TreeNode,int>();
        
        // Encodes a tree to a single string.
        public string serialize(TreeNode root) 
        {
            if(root == null)
                return string.Empty;
                
            List<string> serialized = new List<string>();
            Queue<TreeNode> q = new Queue<TreeNode>();
            q.Enqueue(root);
            
            while(q.Count > 0)
            {
                var node = q.Dequeue();
                serialized.Add(node.val.ToString());
                
                if(node.left != null)
                    q.Enqueue(node.left);
                    
                if(node.right != null)
                    q.Enqueue(node.right);
            }
            
            return string.Join(",", serialized.ToArray());
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(string data) 
        {
            if(string.IsNullOrEmpty(data))
                return null;
                
            string[] tokens = data.Split(',');
            TreeNode root = new TreeNode(int.Parse(tokens[0]));
            Queue<TreeNode> parents = new Queue<TreeNode>();
            parents.Enqueue(root);
            int childIt = 1;
            
            while(childIt < tokens.Length)
            {
                var parent = parents.Dequeue();
                int childVal = int.Parse(tokens[childIt]);
                
                // Can this be the parent's left child?
                if(childVal < parent.val && (lowerBound.ContainsKey(parent) ? (childVal > lowerBound[parent]) : true))
                {
                    parent.left = new TreeNode(childVal);
                    upperBound.Add(parent.left, parent.val);
                    
                    // Inherit parent's lower bound
                    if(lowerBound.ContainsKey(parent))
                        lowerBound.Add(parent.left, lowerBound[parent]);
                        
                    parents.Enqueue(parent.left);
    
                    if(++childIt == tokens.Length)
                        break;
                    
                    childVal = int.Parse(tokens[childIt]);
                }
                
                // Can this be the parent's right child?
                if(childVal > parent.val && (upperBound.ContainsKey(parent) ? (childVal < upperBound[parent]) : true))
                {
                    parent.right = new TreeNode(childVal);
                    lowerBound.Add(parent.right, parent.val);
                    
                    // Inherit parent's upper bound
                    if(upperBound.ContainsKey(parent))
                        upperBound.Add(parent.right, upperBound[parent]);
                        
                    parents.Enqueue(parent.right);
                    ++childIt;
                }
            }
            
            return root;
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));
    

Log in to reply
 

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