剑指offer-61-二叉树序列化

思路

• 递归，先序遍历，把左子树用括号括起来,6!{#!}7!
  解码就是去括号

代码

import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        if(root==null){return "#!";}
        String res=root.val+"!";
        return res+"{"+Serialize(root.left)+"}"+Serialize(root.right);
  }
    TreeNode Deserialize(String str) {
        if(str.length()<=0 || str.charAt(0)=='#'){return null;}
        int p=0;
        while(p<str.length() && str.charAt(p)!='!'){
            p++;
        }
        TreeNode root=new TreeNode(Integer.parseInt(str.substring(0,p)));
        p++;
        int start=p;//当前p为{
        int cnt=1;
        while(cnt>0){
            p++;
            if(str.charAt(p)=='}'){
                cnt--;
            }
            if(str.charAt(p)=='{'){
                cnt++;
            }
        }
        root.left=Deserialize(str.substring(start+1,p));
        root.right=Deserialize(str.substring(p+1));
       return root;
  }
}