Java Morris Preorder and using Stack to deserialize


  • 0

    Null values are avoided in serialization to make the encoded string as compact as possible.
    Using Morris Preorder, encoded string is generated.
    While deserializing, we are using stack and BST property to reconstruct the tree and handle duplicates.

    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder s = new StringBuilder("");
            boolean first_val = true;        
            while(root != null)
            {
                if(root.left == null)
                {
                    if(first_val)
                    {
                        s.append(String.valueOf(root.val));
                        first_val = false;
                    }
                    else
                    {
                        s.append(","+String.valueOf(root.val));
                    }
                    
                    root = root.right;
                }
                else
                {
                    TreeNode temp = root.left;
                    while(temp.right != null && temp.right != root)
                        temp = temp.right;
                    
                    if(temp.right == null)
                    {
                        temp.right = root;
                        
                        if(first_val)
                        {
                            s.append(String.valueOf(root.val));
                            first_val = false;
                        }
                        else
                            s.append(","+String.valueOf(root.val));
                            
                        root = root.left;
                    }
                    else if(temp.right == root)
                    {
                        root = temp.right.right;
                        temp.right = null;
                    }
                }
            }
            
            //System.out.println(s.toString());
            
            return s.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] nodes = data.split(","); 
            
            int val = 0;
            TreeNode root = null,last_popped = null;
            Stack<TreeNode> st = new Stack<TreeNode>();        
            
            for(int i=0;i<nodes.length;++i)
            {
                if(nodes[i].equals(""))
                    return null;
                TreeNode x = new TreeNode(Integer.parseInt(nodes[i]));
                
                if(root == null)
                    root = x;
                else
                {
                    last_popped = null;
                    while(!st.isEmpty())
                    {
                        if(st.peek().val >= x.val)
                        {
                            if(last_popped != null)
                                last_popped.right = x;
                            else
                                st.peek().left = x;
                            last_popped = null;
                            break;
                        }
                        else 
                            last_popped = st.pop();
                    }
                }
                
                if(last_popped != null)
                    last_popped.right = x;
                
                st.push(x);
            }
            
            return root;
        }
    }
    

Log in to reply
 

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