程序员代码面试指南第二版 35.二叉树的序列化和反序列化

二叉树被记录为文件的过程叫作二叉树的序列化，通过文件内容重建原来二叉树的过程叫作二叉树的反序列化，给定一颗二叉树，请将该二叉树先序序列化和层序序列化。
假设序列化的结果字符串为 str，初始时 str = ""，遍历二叉树时，遇到 null 节点，则在 str 的末尾加上 "#!"，否则加上"当前的节点值!"。

输入描述:
第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出描述:
输出两行分别表示该二叉树的先序序列化和层序序列化

示例1

输入
2 1
1 2 0
2 0 0

输出
1!2!#!#!#!
1!2!#!#!#!

读文件细节
InputStreamReader isr = new InputStreamReader(new FileInputStream("a.txt")); // 使用默认字符集(视系统决定)
InputStreamreader isr2 = new InputStreamReader(new FileInputStream("a.txt"), "utf-8"); // 使用GBK字符集
FileReader fr = new FileReader("a.txt");
上面三句代码的功能是一样的, 其中第三句是最方便的, 但要注意, 使用子类只是使用上的方便, 并没有提高效率

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Stack;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] str = sc.nextLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int rootVal = Integer.parseInt(str[1]);
        TreeNode[] nodes = new TreeNode[n+1];
        for(int i=1; i<=n; i++)
            nodes[i] = new TreeNode(i);
        for(int i=1; i<=n; i++){
            str = sc.nextLine().split(" ");
            int val =  Integer.parseInt(str[0]);
            int left = Integer.parseInt(str[1]);
            int right = Integer.parseInt(str[2]);
            nodes[val].left = left==0?null:nodes[left];
            nodes[val].right = right==0?null:nodes[right];
        }
        TreeNode root = nodes[rootVal];
        //
        String res1 = preSerialize2(root);
        System.out.println(res1);
        String res2 = levelSerialize(root);
        System.out.print(res2);
    }
//前序遍历方式序列化; 序列化的关键在于保存结构信息
    public static String preSerialize(TreeNode root){
        //base case
        if(root==null)
            return "#!";
        //
        String cur = root.val+"!";
        String leftRes = preSerialize(root.left);
        String rightRes = preSerialize(root.right);
        return cur+leftRes+rightRes;
    }
    //前序遍历非递归版
    public static String preSerialize2(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        String res = "";
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur==null)
                sb.append("#!");
//                res = res + "#!";
            else{
                sb.append(cur.val).append("!");
//                res = res + cur.val + "!";
                stack.push(cur.right);
                stack.push(cur.left);
            }
        }
//        return res;
        return sb.toString();
    }
    public static TreeNode deserializePre(String s){
        String[] str = s.split("!");
        return core(str);
    }
    public static int index=0;
    public static TreeNode core(String[] str){
        //base case
        if(str[index].equals("#")){
            index++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(str[index]));
        index++;
        node.left = core(str);
        node.right = core(str);
        return node;
    }

    public static TreeNode deserializeLevel(String s){
        String[] str = s.split("!");
        return core2(str);
    }
    public static TreeNode core2(String[] str){
        LinkedList<TreeNode> queue = new LinkedList<>();
        int index = 0;
        TreeNode root = createNode(str[index++]);
        if(root==null)
            return null;
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            cur.left = createNode(str[index++]);
            cur.right = createNode(str[index++]);
            if(cur.left!=null)
                queue.add(cur.left);
            if(cur.right!=null)
                queue.add(cur.right);
        }
        return root;
    }
    public static TreeNode createNode(String s){
        if(s.equals("#"))
            return null;
        return new TreeNode(Integer.parseInt(s));
    }
    public static boolean isEqual(TreeNode root1, TreeNode root2){
        if(root1==null && root2==null)
            return true;
        if((root1==null&&root2!=null) || (root1!=null && root2==null))
            return false;
        return root1.val==root2.val && isEqual(root1.left, root2.left) && isEqual(root1.right, root2.right);
    }
    //层序遍历方式序列化; 层序遍历并不是递归, 而是通过队列实现
    public static String levelSerialize(TreeNode root){
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        String res = "";
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur==null)
                sb.append("#!");
//                res = res + "#!";
            else{
//                res = res + cur.val + "!";
                sb.append(cur.val+"!");
                //只要cur不是null, 就将cur的左右孩子加入队列, 不管左右孩子是否为null
                queue.add(cur.left);
                queue.add(cur.right);
            }
        }
        return sb.toString();
//        return res;
    }
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val = val;
        }
    }
}