树/链表 - 二叉树序列化 - 《leetcode》

1.前序/后序
- 序列化：使用全局变量stringBuilder
- 反序列化：使用全局index
2.层次序列化
- 使用队列保存左右子树的相对顺序
- 反序列化代码框架为BFS
3.重复子树
- HashMap + 后序序列化
4.前(后)序，中序构建二叉树

1.前序/后序

序列化：使用全局变量stringBuilder

public String serialize(TreeNode root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();
        serializeCore(root,sb);
        return sb.toString();
}
String NULL = "#";
String SEP = ",";
public void serializeCore(TreeNode root,StringBuilder sb) {
    if(root == null) {
        sb.append(NULL).append(SEP);
        return;
    }
    sb.append(root.val).append(SEP); //前序
    serializeCore(root.left,sb);
    serializeCore(root.right,sb);
    // sb.append(root.val).append(SEP); //后序
}

反序列化：使用全局index

public TreeNode deserialize(String data) {
        if(data.equals("")) return null;
        nodes = data.split(SEP);
        return deserializeCore();
}
String[] nodes;
int idx = -1;   //Index标记数组已经反序列化的位置 前序
//int idx = nodes.length;  // 后序
public TreeNode deserializeCore() {
    idx++; //index--;
    String parent = nodes[idx];
    TreeNode node = null;
    if(parent.equals(NULL)){
        return node;
    }else{
        node = new TreeNode(Integer.parseInt(parent));
        node.left = deserializeCore();
        node.right = deserializeCore();
    }
    return node;
}

2.层次序列化

使用队列保存左右子树的相对顺序

String SEP = ",";
String NULL = "#";
String serialize(TreeNode root) {
    if (root == null) return "";
    StringBuilder sb = new StringBuilder();
    // 初始化队列，将 root 加入队列
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        /* 层级遍历代码位置 */
        if (cur == null) {
            sb.append(NULL).append(SEP);
            continue;
        }
        sb.append(cur.val).append(SEP);
        /*****************/
        q.offer(cur.left);
        q.offer(cur.right);
    }
    return sb.toString();
}

反序列化代码框架为BFS

* 将字符串反序列化为二叉树结构 */
TreeNode deserialize(String data) {
    if (data.isEmpty()) return null;
    String[] nodes = data.split(SEP);
    // 第一个元素就是 root 的值
    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
    // 队列 q 记录父节点，将 root 加入队列
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    for (int i = 1; i < nodes.length; ) {
        // 队列中存的都是父节点
        TreeNode parent = q.poll();
        // 父节点对应的左侧子节点的值
        String left = nodes[i++];
        if (!left.equals(NULL)) {
            parent.left = new TreeNode(Integer.parseInt(left));
            q.offer(parent.left);
        } else {
            parent.left = null;
        }
        // 父节点对应的右侧子节点的值
        String right = nodes[i++];
        if (!right.equals(NULL)) {
            parent.right = new TreeNode(Integer.parseInt(right));
            q.offer(parent.right);
        } else {
            parent.right = null;
        }
    }
    return root;
}

3.重复子树

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。 leetcode 652

HashMap + 后序序列化

通过拼接字符串的方式把二叉树序列化，后序遍历，当序列化整棵树时，子树已经被比较完成
将子树的序列化结果保存到map中

如果map中存在相同的序列化子树，则将该子树的根节点加入结果集 ```java class Solution { HashMap dict = new HashMap(); ArrayList res = new ArrayList(); public List findDuplicateSubtrees(TreeNode root) {

 traverse(root);
 return res;

}

public String traverse(TreeNode root) {

 if(root == null) return "#";

 String left = traverse(root.left);
 String right = traverse(root.right);

 String strTree =  root.val + ","+left +","+ right;

 int cnt = dict.getOrDefault(strTree,0);

 if(cnt == 1){  // 只在cnt == 1时，添加到结果集，防止重复
     res.add(root);
 }

 dict.put(strTree,cnt+1); 

 return strTree;

}

} ```

二叉树序列化