LeetCode 297 Serialize and Deserialize Binary Tree

思路

Serialize：用arraylist代替queue进行bfs，使用index来完成，把所有节点加入一个arraylist，然后再统一转成字符串(StringBuilder)。注意需要在把所有节点加入arraylist后，进行从后往前的删除null值。
Deserialize: 同样使用一个arraylist，使用一个index来标记当前根节点，同时使用isLeftChild标记当前应该生成左子节点还是右子节点。
注意在使用arraylist的时候应该使用size作为判断条件，因为size一直在增加，这样可以构成合理的循环条件。

复杂度

时间复杂度O(n)
空间复杂度O(n)

代码

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
public class Codec {
    // Encodes a tree to a single string.public String serialize(TreeNode root) {
    String res = "";if (root == null) {
    return res;}List<TreeNode> queue = new ArrayList<>();queue.add(root);for (int i = 0; i < queue.size(); i++) {
    TreeNode node = queue.get(i);if (node == null) {
    continue;}queue.add(node.left);queue.add(node.right);}while (queue.get(queue.size() - 1) == null) {
    queue.remove(queue.size() - 1);}StringBuilder sb = new StringBuilder();sb.append(queue.get(0).val);for (int i = 1; i < queue.size(); i++) {
    if (queue.get(i) != null) {
    sb.append(",");sb.append(queue.get(i).val);} else {
    sb.append(",#");}}return sb.toString();}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {
    if (data.length() == 0) {
    return null;}String[] value = data.split(",");List<TreeNode> queue = new ArrayList<>();TreeNode root = new TreeNode(Integer.parseInt(value[0]));queue.add(root);int index = 0;boolean isLeftChild = true;for (int i = 1; i < value.length; i++) {
    if (!value[i].equals("#")) {
    TreeNode node = new TreeNode(Integer.parseInt(value[i]));if (isLeftChild) {
    queue.get(index).left = node;} else {
    queue.get(index).right = node;}queue.add(node);}if (!isLeftChild) {
    index++;}isLeftChild = !isLeftChild;}return root;}
}// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));