题目
剑指 Offer 37. 序列化二叉树
我的思路
从树变成题目要求的字符串,借助队列层序遍历即可。注意整数变成字符串可以用输出运算符<<。
从一个层序遍历的字符串序列转化为一颗二叉树,可以考虑完全二叉树的特性,一个节点i的孩子是2i和2i+1。
技巧:
stoi(string val)函数字符串转整数
上面的写法,利用输入运算符,可以连续读取多个被空格间隔的字符串。直到读取到终止符
我的实现
题解的实现
/** * 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 "; } } return out.str(); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { istringstream input(data); string val; vector<TreeNode*> vec; while (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));