题目链接

LeetCode
LeetCode

题目描述

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

示例:

你可以将以下二叉树：

1<br />   / \<br />   2   3<br />        / \<br />       4   5

序列化为 “[1,2,3,null,null,4,5]”

解题思路

代码中遇到的数据流知识点在https://www.yuque.com/gongwf/coding/tkxgb0中

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream out;
        queue<TreeNode*> q;
        q.push(root);//层次遍历
        while (!q.empty()) {
            TreeNode* tmp = q.front();
            q.pop();
            if (tmp) {
                out<<tmp->val<<",";
                q.push(tmp->left);
                q.push(tmp->right);
            } else {
                out<<"null,";
            }
        }
        string ret = out.str();
        ret = ret.substr(0,ret.size()-1);
        return ret;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        string val;
        vector<TreeNode*> vec;
        while (getline(input,val, ',')) {
            if (val == "null") {
                vec.push_back(NULL);
            } else {
                vec.push_back(new TreeNode(stoi(val)));
            }
        }
        int j = 1;                                          // i每往后移动一位，j移动两位，j始终是当前i的左子下标
        for (int i = 0; j < vec.size(); ++i) {              // 肯定是j先到达边界，所以这里判断j < vec.size()
            if (vec[i] == NULL) continue;                   // vec[i]为null时跳过。
            if (j < vec.size()) vec[i]->left = vec[j++];    // 当前j位置为i的左子树
            if (j < vec.size()) vec[i]->right = vec[j++];   // 当前j位置为i的右子树
        }
        return vec[0];
    }

};

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

/**
 * 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();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode tmp = q.poll();
            if(tmp != null){
                sb.append(String.valueOf(tmp.val) + ',');
                q.offer(tmp.left);
                q.offer(tmp.right);
            }else{
                sb.append("null,");
            }
        }
        String res = sb.toString();
        // 去掉最后一个","
        return res.substring(0, res.length());
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 切割字符串
        String[] dataArr = data.split(",");
        // TreeNode 保存结点
        TreeNode[] nodeArr = new TreeNode[dataArr.length];
        for(int i = 0; i < nodeArr.length; ++i){
            // 当前字符串不是null
            if(dataArr[i].charAt(0) != 'n'){
                // 字符串转数字
                nodeArr[i] = new TreeNode(Integer.valueOf(dataArr[i]));
            }else{
                nodeArr[i] = null;
            }
        }
        // 连接左右结点
        int j = 1;
        for(int i = 0; j < nodeArr.length; ++i){
            if(nodeArr[i] == null){
                continue;
            }
            if(j < nodeArr.length)
                nodeArr[i].left = nodeArr[j++];
            if(j < nodeArr.length)
                nodeArr[i].right = nodeArr[j++];
        }
        return nodeArr[0];
    }
}

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