剑指Offer-62. 序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

思路

采用前序遍历

TreeNode -> String，用 # 表示空格，用 ! 表示一个结点的结束

String -> TreeNode

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {

    // 用一个变量记录索引，保证每次使用的是新的根结点
    private int index = 0;

    // 序列化
    String Serialize(TreeNode root) {

        StringBuilder sb = new StringBuilder();

        if (root == null) {
            sb.append("#!");
            return sb.toString();
        } else {
            sb.append(root.val + "!");
            sb.append(Serialize(root.left));
            sb.append(Serialize(root.right));
        }

        return sb.toString();
  }
    // 反序列化
    TreeNode Deserialize(String str) {

        String[] nodes = str.split("!");
        TreeNode node = null;

        if (nodes[index].equals("#")) {
            index++;
            return null;
        } else {
            node = new TreeNode(Integer.valueOf(nodes[index]));
            index++;
            node.left = Deserialize(str);
            node.right = Deserialize(str);
        }

        return node;
  }
}

上面这个能通过大部分测试用例，但是在 leetcode 上就会 TLE

成功通过 leetcode 全部测试用例的代码如下，使用了 Deque 双端队列来存储结点

/**
 * 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) {

        StringBuilder sb = new StringBuilder();

        if (root == null) {
            sb.append("#!");
        } else {
            sb.append(root.val + "!");
            sb.append(serialize(root.left));
            sb.append(serialize(root.right));
        }

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        Deque<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split("!")));

        return preOrder(nodes);
    }

    public TreeNode preOrder(Deque<String> nodes) {

        TreeNode node = null;
        String val = nodes.remove();

        if (val.equals("#")) {
            return null;
        } else {
            node = new TreeNode(Integer.valueOf(val));
            node.left = preOrder(nodes);
            node.right = preOrder(nodes);
        }

        return node;

    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));