Ac solution code


  • 1

    Special thanks to @gavinlinasd

    This solution is based on pre-order traversal.

    Serialize: Use pre-order traversal to encode nodes to string, mark null as "null", with "," as the splitter.
    Append the string of node, node's left, node'right to the result recursively.

    Deserialize:
    Decode the string list of nodes, also in the pre-order sequence.

    public class Codec {
    	private final String splitter = ",";
    	private final String NULL_MARK = "null";
    	
        public String serialize(TreeNode root) {// Encodes a tree to a single string.
        	StringBuilder sb = new StringBuilder();
        	buildString(root, sb);
        	return sb.toString(); 
        }
        
        void buildString(TreeNode root, StringBuilder sb) {
        	if (root == null) {
        		sb.append(NULL_MARK).append(splitter);
        		return;
        	} else {
    	    	sb.append(root.val).append(splitter);    	
    	    	buildString(root.left, sb);
    	    	buildString(root.right, sb);    	
    	    }
        }
        
        public TreeNode deserialize(String data) {
        	String strs[] = data.split(splitter);
            return buildTree(new LinkedList<String>(Arrays.asList(strs)));
        }
        
        TreeNode buildTree(List<String> list) {
        	String str = list.remove(0);
        	if (str.equals(NULL_MARK)) return null;
        	TreeNode root = new TreeNode(Integer.valueOf(str));
        	root.left = buildTree(list);
        	root.right = buildTree(list);    	
        	return root;
        }
    
    //	public static void main(String args[]) {// Test cases	
    //		TreeNode root = new TreeNode(4);
    //		root.left = new TreeNode(2);
    //		root.right = new TreeNode(5);
    //		root.left.left = new TreeNode(1);
    //		root.left.right = new TreeNode(3);
    //
    //		String str = new Codec().serialize(root);
    //		TreeNode node = new Codec().deserialize(str);
    //		String str2 = new Codec().serialize(node);
    //		
    //	}
    }
    

Log in to reply
 

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