recursion solution. preorder traversal. add empty node represented in String "n" for 'null' child.


  • 1

    recursion solution. preorder traversal. add empty node represented in String "n" for 'null' child. Thus every node would have 2 children or 0 children, there's no case that a node has exactly 1 child. Then took advantage of this in deserialization, just like decoding the encoding tree of Huffman tree .

    i.e. :
    TreeNode node7 = new TreeNode(7, null, null);
    TreeNode node8 = new TreeNode(8, null, null);
    TreeNode node9 = new TreeNode(9, null, null);
    TreeNode node4 = new TreeNode(4, node7, null);
    TreeNode node5 = new TreeNode(5, null, node8);
    TreeNode node6 = new TreeNode(6, null, node9);
    TreeNode node2 = new TreeNode(2, node4, node5);
    TreeNode node3 = new TreeNode(3, node6, null);
    TreeNode node1 = new TreeNode(1, node2, node3);
    BinaryTree tree = new BinaryTree(node1);

    serialized string would be "1,2,4,7,n,n,n,5,n,8,n,n,3,6,n,9,n,n,n".

    import java.util.concurrent.atomic.AtomicInteger;

    public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) {
            return "n";
        }
        
        return new StringBuffer().append(root.val).append(",")
                   .append(serialize(root.left)).append(",")
                   .append(serialize(root.right)).toString();
        
    }
    
    // Decodes your encoded data to tree.
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
    	return deserialize(data, new AtomicInteger(0));
    }
    
    public TreeNode deserialize(String data, AtomicInteger start) {
        TreeNode node = null;
        if(data == null || data.length() == 0) {
        	return null;
        }
        // parse the value from the string,
        String nodeVal;
        int commaIndex = data.indexOf((int)',', start.intValue());
        if(commaIndex == -1) {
        	nodeVal = data.substring(start.intValue());
        } else {
            nodeVal = data.substring(start.intValue(), commaIndex);
        }
        
        System.out.println("val: " + nodeVal);
        start.set(commaIndex + 1);
        
        // if it's null, then return null
    	if("n".equals(nodeVal)) {
    		return null;
    	} else {
    		// not null
    		node = new TreeNode(Integer.valueOf(nodeVal).intValue());
    		node.left = deserialize(data, start);
    		node.right = deserialize(data, start);
    		return node;
    	}
    }
    

    }


Log in to reply
 

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