LeetCode刷题实战297:二叉树的序列化与反序列化
示例
解题
/**
* 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) {
if ( root == nullptr ) return "";
string ans = "";
serializeCore( root, ans );
return ans;
}
void serializeCore( TreeNode* node, string& seq ) {
if ( node == nullptr ) {
seq += '#';
return;
}
seq += to_string( node->val ) + '!';
serializeCore( node->left, seq );
serializeCore( node->right, seq );
return;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if ( data == "" )
return nullptr;
int index = 0;
return deserializeCore( data, index );
}
TreeNode* deserializeCore( string& str, int& index ) {
if ( str[index] == '#' ) {
++index;
return nullptr;
}
int left = index;
while ( str[index] != '!' )
++index;
string temp = str.substr( left, index - left );
TreeNode* node = new TreeNode( stoi( temp ) );
++index;
node->left = deserializeCore( str, index );
node->right = deserializeCore( str, index );
return node;
}
int stoi( string& str ) {
int res = 0;
int sign = 1;
int i = 0;
if ( str[0] == '-' ) {
sign = -1;
i = 1;
}
while ( i < str.size() )
res = res * 10 + ( str[i++] - '0' );
return sign * res;
}
};
评论