Java solution with preorder traversal, space optimize, beat 99.29%


  • 0

    The idea is from this lecture slide. http://www.cs.usfca.edu/~brooks/S04classes/cs245/lectures/lecture11.pdf

    Use an indicator ('*') to mark internal nodes, use "n" to mark a null node. If the node is a leaf node, just add the value.

    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            //preorder
            if(root == null){
                return "";
            }
            
            StringBuilder sb = new StringBuilder();
            
            helper(sb, root);
            
            return sb.toString();
        }
        
        public void helper(StringBuilder sb, TreeNode root){
            if(root==null){
                sb.append("n,");
                return;
            }
            
            sb.append(root.val);
            
            if(root.left == null && root.right == null){
                sb.append(",");
            }else{
                // if the node is an internal node, mark it value with a '*' to indicate.
                sb.append("*,");
                helper(sb, root.left);
                helper(sb, root.right);
            }
            
        }
    
        // Decodes your encoded data to tree.
        int index =0;
        public TreeNode deserialize(String data) {
            if(data.equals("")){
                return null;
            }   
            
            String[] values = data.split(",");
            TreeNode root = dHelper(values);
            return root;
        }
        
        public TreeNode dHelper(String[] values){
            if(index >= values.length || values[index].equals("n")){
                index++;
                return null;
            }
            
            String val = values[index];
            index++;
            if(val.charAt(val.length()-1) =='*'){
                // means it has child;
                val = val.substring(0, val.length()-1);
                int data = Integer.parseInt(val);
                
                TreeNode node = new TreeNode(data);
                
                node.left = dHelper(values);
                node.right = dHelper(values);
                
                return node;
                
            }else{
                // its the leaf
                TreeNode node = new TreeNode(Integer.parseInt(val));
                
                return node;
            }
            
        }
    }
    

    Runtime: 12ms, beat 99.29%;


Log in to reply
 

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