【剑指offer】序列化二叉树

解题思路

序列化时，可以通过各种遍历方法，例如层序遍历、递归遍历对二叉树进行遍历，遍历过程中将每个节点的值拼接到字符串中，注意每个节点之间用一个标识符隔开，例如,，这是为了防止节点的值超过个位数。

反序列化则根据序列化的过程进行相应的解码，不同的反序列化方式有不同的技巧，下面分别使用层序遍历和先序遍历两种方法进行求解。

解法一：层序遍历

• 序列化：通过队列进行遍历，然后生成序列化的字符串，比较常规。
• 反序列化：稍微有点难度。首先对res按照,进行切分得到String数组strs，每个位置表示一个节点的值。和序列化一样，也需要使用一个队列进行操作，注意每次需要取数组strs中的两个元素，即构建当前节点的左右子树，然后分别把左右子树加入队列中。

import java.util.*;

public class Solution {
    
    String Serialize(TreeNode root) {
    
        String str = "";
        if (root == null)
            return str;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        str += root.val + ",";
        while (!queue.isEmpty()) {
    
            TreeNode top = queue.poll();
            if (top.left == null)
                str += "#";
            else {
    
                queue.add(top.left);
                str += top.left.val;
            }
            str += ',';
            if (top.right == null)
                str += "#";
            else {
    
                queue.add(top.right);
                str += top.right.val;
            }
            str += ',';
        }
        return str;
    }

    TreeNode Deserialize(String str) {
    
        if (str.length() == 0)
            return null;
        int i = 1;
        String strList[] = str.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(strList[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
    
            TreeNode top = queue.poll();
            // 左子树
            if (strList[i].equals("#"))
                top.left = null;
            else {
    
                top.left = new TreeNode(Integer.parseInt(strList[i]));
                queue.add(top.left);
            }
            i++;
            // 右子树
            if (strList[i].equals("#"))
                top.right = null;
            else {
    
                top.right = new TreeNode(Integer.parseInt(strList[i]));
                queue.add(top.right);
            }
            i++;
        }
        return root;
    }
}

解法二：先序遍历

• 序列化：定义全局字符串res，递归的时候记录遍历到的节点值，遍历完一个节点后，在其后加,标识符。
• 反序列化：稍微有点难度。首先对res按照,进行切分得到String数组strs，每个位置表示一个节点的值。定义全局变量ind，用来记录当前遍历到strs的位置，如果当前位置是#，表示为空，直接返回null；否则新建一个节点node，并递归构建其左右子树，注意，在递归前判断数组是否越界，如果inds++后等于strs的长度，则表明已经遍历完数组，此时返回node（注意数组越界的判断不能放在开头，否则会写不下去，因为不知道返回什么了）

import java.util.*;

public class Solution {
    
    public String res = "";
    public int ind = 0;

    String Serialize(TreeNode root) {
    
        if (root == null) {
    
            res += "#,";
            return res;
        }
        res += root.val + ",";
        Serialize(root.left);
        Serialize(root.right);
        return res;
    }

    TreeNode deserialize(String[] strs) {
    
        if (strs[ind].equals("#")) {
    
            ind++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(strs[ind]));
        ind++;
        if (ind >= strs.length)
            return node;
        node.left = deserialize(strs);
        node.right = deserialize(strs);
        return node;
    }

    TreeNode Deserialize(String str) {
    
        String[] strs = str.split(",");
        return deserialize(strs);
    }
}