【剑指offer】面试题37：序列化二叉树

ゞ浴缸里的玫瑰 2022-03-27 05:30 144阅读 0赞

> **题目：请实现两个函数，分别用来序列化和反序列化二叉树。**

如果二叉树的序列化是从根节点开始的，那么相应的反序列化在根节点的数值读出来的时候就可以开始了。因此，我们根据**前序遍历**的顺序来序列化二叉树，因为前序遍历是从根节点开始的。在遍历二叉树碰到 null 指针时，这些 null 指针序列化成为一个特殊的字符（如“\#”）。

**序列化和反序列化的过程都是将二叉树分解为 3 部分：根节点、左子树和右子树。我们在处理（序列化和反序列化）它的根节点之后再分别处理它的左、右子树。这就是典型的把问题递归分解然后逐个解决的过程。**

/**
     * 请实现两个函数，分别用来序列化和反序列化二叉树
     */
    public class SerializeAndDeserialize {
    
    	public class TreeNode{
    		int val = 0;
    		TreeNode left = null;
    		TreeNode right = null;
    	
    		public TreeNode(int val){
    			this.val = val;
    		}
    	}
    	
    	int index = -1;   // 计数变量
    	
    	// 将树序列化成字符串
    	public String serialize(TreeNode root){
    		StringBuilder sb = new StringBuilder();
    		
    		if(root == null){
    			sb.append("#,");
    			return sb.toString();
    		}
    		
    		sb.append(root.val + ",");
    		sb.append(serialize(root.left));
    		sb.append(serialize(root.right));
    		
    		return sb.toString();
    	} 
    	
    	// 将字符串反序列化成树
    	public TreeNode deserialize(String str){
    		index++;
    		String[] string = str.split(",");
    		TreeNode node = null;
    		if(!string[index].equals("#")){
    			node = new TreeNode(Integer.valueOf(string[index]));
    			node.left = deserialize(str);
    			node.right = deserialize(str);
    		}
    		return node;
    	}
    }