思路: 二叉树的各种顺序中,随便挑1种,遍历每个节点, 拼装出1个字符串即可实现序列化。要注意的是, 空节点也需要, 可以找一个特殊符号比如#表示。 反序列化则是相反的过程,解析该字符串即可。
这里用层序遍历来实现一把:
序列化代码:
public static String serial(TreeNode node) { StringBuilder sb = new StringBuilder(); if (node == null) { sb.append("#_"); return sb.toString(); } Queue<TreeNode> queue = new LinkedList<>(); queue.add(node); while (!queue.isEmpty()) { TreeNode n = queue.poll(); sb.append(n == null ? "#_" : n.val + "_"); if (n != null) { queue.add(n.left); queue.add(n.right); } } //注:0位置占位不用, 方便后面反序列化 return "*_" + sb.toString(); }
假设有一颗树:
把空节点补全后,如下图:
序列化后为 *_1_2_3_4_5_#_7_#_#_#_#_#_#_ 按"_"拆分成String[]后,就变成了二叉树的数组存储 , 如果根节点的下标从1算起,每个元素的左孩子索引为2*i,右孩子索引为2*i+1 ,它的父节点索引为i/2 (这也是为啥第0个元素要用*占位的原因),根据这个特性, 很容易可以写反序列化的代码:
public static TreeNode deSerial(String str) { if (str == null || str.length() <= 0) { return null; } String[] arr = str.split("_"); TreeNode root = new TreeNode(Integer.parseInt(arr[1])); Map<Integer, TreeNode> parentMap = new HashMap<>(); parentMap.put(1, root); int curr = 1; while (curr < (arr.length >> 1)) { int leftIndex = curr << 1; int rightIndex = (curr << 1) + 1; String leftVal = arr[leftIndex]; String rightVal = arr[rightIndex]; if (!"#".equals(leftVal)) { TreeNode leftNode = new TreeNode(Integer.parseInt(leftVal)); int parentIndex = leftIndex >> 1; parentMap.get(parentIndex).left = leftNode; parentMap.put(leftIndex, leftNode); } if (!"#".equals(rightVal)) { TreeNode rightNode = new TreeNode(Integer.parseInt(rightVal)); int parentIndex = rightIndex >> 1; parentMap.get(parentIndex).right = rightNode; parentMap.put(rightIndex, rightNode); } curr++; } return root; }