题解 | #序列化二叉树#TOP39

思路:
1.递归，最要是考虑好空节点用什么符号代替和解析
2.前序遍历，如果是空节点则用$! ,每个节点后加!
3.使用栈的形式实现前序遍历，序列化会有问题，没有解决，后改为递归

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        if(root == null) {
			return "$!";
		}
        //前序遍历
        StringBuilder sb = new StringBuilder();
		scr(root, sb);
		return sb.toString();
     }
    private  void scr(TreeNode root, StringBuilder result){
        if(root == null){
            result.append("$!");
            return;
        }
        result.append(root.val+"!");
		scr(root.left, result);
		scr(root.right, result);
    }
    TreeNode Deserialize(String str) {
       if("$!".equals(str)){
           return null;
       }
        Queue<String> queue = new LinkedList<>();
        String[] result = str.split("!");
        for(int i = 0;i<result.length;i++) {
            queue.add(result[i]);
        }
        return descr(queue);
    }
    private TreeNode descr(Queue<String> queue){
        //根
        String value = queue.poll();
        if("$".equals(value)){
            return null;   
        }
        TreeNode node = new TreeNode(Integer.parseInt(value));
        node.left = descr(queue);
        node.right = descr(queue);
        return node;
    }
}