《剑指offer》面试题37. 序列化二叉树

问题描述

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

示例: 

你可以将以下二叉树：

    1

   / \

  2   3

     / \

    4   5

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

代码

这种方法使用了二叉树的层序遍历，第二部分相当于把一个层序遍历的数组重新转化为一个二叉树，构造一个虚拟的节点ans,ans->right指向根节点，也就是要返回的答案，使用left来判断应该添加在根节点的哪一个子节点上。

/**

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

        string ans;

        if(!root)return ans;

        queue<TreeNode*> q;

        TreeNode * node;

        int size;

        q.push(root);

        while(!q.empty())

        {

            size = q.size();

            for(int i = 0; i < size; ++i)

            {

                node = q.front();

                q.pop();

                if(node){

                    ans += to_string(node->val) + ',';

                    q.push(node->left);

                    q.push(node->right);

                }

                else{

                    ans += "null,";

                }

            }

        }

        if(!ans.size())ans.pop_back();

        return ans;

    }

    // Decodes your encoded data to tree.

    TreeNode* deserialize(string data) {

        unique_ptr<TreeNode> ans(new TreeNode(0));

        queue<TreeNode*> q;

        q.push(ans.get());

        int beg = 0,end = 0;

        string s;

        bool left = false;

        while(beg < data.size())

        {

            while(end < data.size() && data[end] != ',')++end;

            s = data.substr(beg,end-beg);

            TreeNode* t = NULL;

            if(s != "null")t = new TreeNode(atoi(s.c_str()));

            auto cur  = q.front();

            if(left){

                cur->left = t;

            }

            else{

                cur->right = t;

                q.pop();//添加完当前节点的右子节点后可以考虑队列中其他节点了

            }

            if(t)q.push(t);

            left = !left;

            beg = ++end;

        }

        return ans->right;

    }

};

// Your Codec object will be instantiated and called as such:

// Codec codec;

// codec.deserialize(codec.serialize(root));

结果

执行用时 :72 ms, 在所有 C++ 提交中击败了43.30%的用户

内存消耗 :29.7 MB, 在所有 C++ 提交中击败了100.00%的用户

也可以使用递归的方法来求解。

巴特西

《剑指offer》面试题37. 序列化二叉树

问题描述

代码

最新文章

热门文章