序列化二叉树

问题描述

请实现两个函数，分别用来序列化和反序列化二叉树。其中序列化的意思返回一个带有逗号和特殊符号的字符串，而反序列化就是根据带有特殊符号和逗号的字符串返回一个二叉树

思路分析

对应序列化二叉树来说，因为每次都是将根结点序列化，所以可用前序遍历，即如果结点有孩子，先保存结点值，在继续，当遇到孩子为空时，就用特殊符号输出代替
反序列化，同样用递归实现，即先利用一个索引，用于取出每次遍历的字符串中的值，同时把字符串变成一个字符数组，然后比较是否是特殊符号，如果是特殊符号，不做处理，反之，变成根结点的孩子

码上有戏

static class TreeNode{
		int data;
		TreeNode left;
		TreeNode right;
		
		public TreeNode(int data){
			this.data=data;
		}
	}
	
	public String serialize(TreeNode root){
	StringBuilder sb=new StringBuilder();
		if(root==null)
		{
		  sb.append("$"+",");
			 return sb.toString();
		}
		       sb.append(root.data+",");
		        sb.append(serialize(root.left));
		         sb.append(serialize(root.right));
		        return sb.toString();
	}
	
	int n=-1;
	public TreeNode deSerialize(String str){
		 n++;
		if(n>=str.length())
			return null;
		  TreeNode node=null;
		 String[] s=str.split(",");
		if(!s[n].equals("$")){
			node=new TreeNode(Integer.parseInt(s[n]));
			  node.left=deSerialize(str);
			  node.right=deSerialize(str);
		}
		 return node;
	}

	void preTraver(TreeNode root){
		if(root!=null){
		System.out.print(root.data+" ");
		 preTraver(root.left);
		  preTraver(root.right);
		}
	}

测试：

TreeNode root=new TreeNode(10);
TreeNode a=new TreeNode(6);
TreeNode b=new TreeNode(14);
TreeNode c=new TreeNode(4);
TreeNode d=new TreeNode(8);
TreeNode e=new TreeNode(12);
TreeNode f=new TreeNode(16);
root.left=a;
root.right=b;
a.left=c;
a.right=d;
b.left=e;
b.right=f;
String s=new ConvertTreeToDLinkList().serialize(root);
System.out.println(s);
TreeNode head=new ConvertTreeToDLinkList().deSerialize(s);
System.out.println();
new ConvertTreeToDLinkList().preTraver(head);

测试结果

10,6,4,$,$,8,$,$,14,12,$,$,16,$,$,
10 6 4 8 14 12 16