The above JSON string represents a binary tree as the following:
2
/ \
1 10
/
5
The solution is quite simpler, since JSON can express tree naturally, Jackson can deal with recursive tree directly. Just annotate a constructor with JsonCreator:
Well, there is a little problem here, the JSON string above is very verbose. Let’s use another kind of serialization format, i.e., serialize a binary tree in level order traversal. For example, the binary tree above can be serialized as the following JSON string:
[2,1,10,null,null,5]
Now how to deserialize this JSON string to a binary tree?
The idea is very similar to my previous article, Deserialize a JSON Array to a Singly Linked List. Just make the BinaryTreeNode implement java.util.list, pretend that it’s a list, write our own deserialization code so that Jackson can treat a binary tree as a list.
The complete code of BinaryTreeNode is as the following:
packageme.soulmachine.customized_collection;importjava.util.*;publicclassBinaryTreeNode<E>extendsAbstractSequentialList<E>implementsCloneable,java.io.Serializable{publicEvalue;publicBinaryTreeNode<E>left;publicBinaryTreeNode<E>right;/** has a left child, but it's a null node. */privatetransientbooleanleftIsNull;/** has a right child, but it's a null node. */privatetransientbooleanrightIsNull;/** * Constructs an empty binary tree. */publicBinaryTreeNode(){value=null;left=null;right=null;}/** * Constructs an binary tree with one element. */publicBinaryTreeNode(finalEvalue){if(value==null)thrownewIllegalArgumentException("null value");this.value=value;left=null;right=null;}/** * Constructs a binary tree containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this binary tree * @throws NullPointerException if the specified collection is null */publicBinaryTreeNode(Collection<?extendsE>c){this();addAll(c);}/** * @inheritDoc * * <p>Note: null in the middle counts, so that each father in the binary tree has a * one-to-one mapping with the JSON array.</p> */publicintsize(){if(value==null)return0;Queue<BinaryTreeNode<E>>queue=newLinkedList<>();queue.add(this);intcount=0;while(!queue.isEmpty()){finalBinaryTreeNode<E>node=queue.remove();++count;if(node.left!=null){queue.add(node.left);}else{if(node.leftIsNull)++count;}if(node.right!=null){queue.add(node.right);}else{if(node.rightIsNull)++count;}}returncount;}/** * Tells if the argument is the index of a valid position for an * iterator or an add operation. */privatebooleanisPositionIndex(intindex){returnindex>=0&&index<=size();}/** * Constructs an IndexOutOfBoundsException detail message. * Of the many possible refactorings of the error handling code, * this "outlining" performs best with both server and client VMs. */privateStringoutOfBoundsMsg(intindex){return"Index: "+index+", Size: "+size();}privatevoidcheckPositionIndex(intindex){if(!isPositionIndex(index))thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));}privateclassNodeAndFather{privateBinaryTreeNode<E>node;privateBinaryTreeNode<E>father;privatebooleanisRight;// the father is the right child of the fatherprivateNodeAndFather(BinaryTreeNode<E>node,BinaryTreeNode<E>father,booleanisRight){this.node=node;this.father=father;this.isRight=isRight;}}/** * Returns the (may be null) Node at the specified element index. */NodeAndFathernode(intindex){checkPositionIndex(index);if(value==null)returnnull;Queue<NodeAndFather>queue=newLinkedList<>();queue.add(newNodeAndFather(this,null,false));for(inti=0;!queue.isEmpty();++i){finalNodeAndFathernodeAndFather=queue.remove();if(i==index){returnnodeAndFather;}if(nodeAndFather.node!=null){queue.add(newNodeAndFather(nodeAndFather.node.left,nodeAndFather.node,false));queue.add(newNodeAndFather(nodeAndFather.node.right,nodeAndFather.node,true));}}thrownewIllegalArgumentException("Illegal index: "+index);}/** * @inheritDoc */publicListIterator<E>listIterator(intindex){checkPositionIndex(index);returnnewListItr(index);}privateclassListItrimplementsListIterator<E>{privateNodeAndFathernext;privateintnextIndex;privateintexpectedModCount=modCount;ListItr(intindex){assertisPositionIndex(index);next=node(index);nextIndex=index;}publicbooleanhasNext(){finalBinaryTreeNode<E>cur=next.node;returncur!=null||(next.father.leftIsNull||next.father.rightIsNull);}//O(n)publicEnext(){checkForComodification();if(!hasNext())thrownewNoSuchElementException();finalEresult=next.node!=null?next.node.value:null;next=node(nextIndex+1);nextIndex++;returnresult;}publicbooleanhasPrevious(){thrownewUnsupportedOperationException();}publicEprevious(){thrownewUnsupportedOperationException();}publicintnextIndex(){thrownewUnsupportedOperationException();}publicintpreviousIndex(){thrownewUnsupportedOperationException();}publicvoidremove(){thrownewUnsupportedOperationException();}publicvoidset(Ee){thrownewUnsupportedOperationException();}publicvoidadd(Ee){// always append at the tailcheckForComodification();if(next==null){// empty listBinaryTreeNode.this.value=e;BinaryTreeNode.this.left=null;BinaryTreeNode.this.right=null;}else{finalBinaryTreeNode<E>newNode=e!=null?newBinaryTreeNode<>(e):null;if(next.father==null){// rootBinaryTreeNode<E>cur=next.node;cur.left=newNode;assertcur.right==null;thrownewUnsupportedOperationException();}else{if(next.isRight){if(next.father.right!=null)thrownewIllegalStateException();next.father.right=newNode;if(newNode==null){next.father.rightIsNull=true;}}else{if(next.father.left!=null)thrownewIllegalStateException();next.father.left=newNode;if(newNode==null){next.father.leftIsNull=true;}}}}modCount++;expectedModCount++;}finalvoidcheckForComodification(){if(modCount!=expectedModCount)thrownewConcurrentModificationException();}}// the following functions are just for unit tests.ArrayList<E>preOrder(){finalArrayList<E>result=newArrayList<>();if(this.value==null){returnresult;}preOrder(this,result);returnresult;}privatestatic<E>voidpreOrder(BinaryTreeNode<E>root,ArrayList<E>result){if(root==null)return;result.add(root.value);if(root.left!=null)preOrder(root.left,result);if(root.right!=null)preOrder(root.right,result);}ArrayList<E>inOrder(){finalArrayList<E>result=newArrayList<>();if(this.value==null){returnresult;}inOrder(this,result);returnresult;}privatestatic<E>voidinOrder(BinaryTreeNode<E>root,ArrayList<E>result){if(root==null)return;if(root.left!=null)inOrder(root.left,result);result.add(root.value);if(root.right!=null)inOrder(root.right,result);}ArrayList<E>postOrder(){finalArrayList<E>result=newArrayList<>();if(this.value==null){returnresult;}postOrder(this,result);returnresult;}privatestatic<E>voidpostOrder(BinaryTreeNode<E>root,ArrayList<E>result){if(root==null)return;if(root.left!=null)postOrder(root.left,result);if(root.right!=null)postOrder(root.right,result);result.add(root.value);}ArrayList<E>levelOrder(){finalArrayList<E>result=newArrayList<>();if(this.value==null){returnresult;}Queue<BinaryTreeNode<E>>queue=newLinkedList<>();queue.add(this);while(!queue.isEmpty()){finalBinaryTreeNode<E>node=queue.remove();result.add(node.value);if(node.left!=null)queue.add(node.left);if(node.right!=null)queue.add(node.right);}returnresult;}}
packageme.soulmachine.customized_collection;importcom.fasterxml.jackson.core.type.TypeReference;importcom.fasterxml.jackson.databind.ObjectMapper;importorg.junit.Test;importjava.io.IOException;importjava.util.Arrays;importjava.util.List;importstaticorg.junit.Assert.assertEquals;publicclassBinaryTreeNodeTest{@TestpublicvoiddeserializeTest()throwsIOException{ObjectMapperobjectMapper=newObjectMapper();finalList<Integer>intList=Arrays.asList(2,1,10,null,null,5);/* 2 / \ 1 10 / 5 */// TODO: the time complexity is O(n^2)finalBinaryTreeNode<Integer>intTree=objectMapper.readValue("[2,1,10,null,null,5]",newTypeReference<BinaryTreeNode<Integer>>(){});assertEquals(intList,intTree);assertEquals(Arrays.asList(2,1,10,5),intTree.levelOrder());assertEquals(Arrays.asList(2,1,10,5),intTree.preOrder());assertEquals(Arrays.asList(1,2,5,10),intTree.inOrder());assertEquals(Arrays.asList(1,5,10,2),intTree.postOrder());}}