来源:EPI, Facebook Interview
原帖:http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html
题目:
A very frequent interview question. Suppose you have a tree, how could you serialize it to file and revert it back? For example,
1
/ \
2 3
\ /
4 5
/ \
6 7
[Thoughts]
一个比较简单直接的做法是,通过前序遍历来做,把所有空节点当做“#”来标示。那么这棵树可以表示为
1
/ \
2 3
/ \ / \
# 4 5 #
/ \
6 7
/ \ / \
# # # #
那么前序遍历的结果就是: {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'}; 代码如下:
参考 http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html
代码:
Deserialize Tree的stack解法
EPI 6.8. pg. 236.
Reconstructing A Binary Tree From A Preorder Traversal With Marker. Design an O(n) time algorithm for reconstructing a binary tree from a preorder visit sequence that uses null to mark empty children. How would you modify your reconstruction algorithm if the sequence corresponded to a postorder or inorder walk.
代码:
原帖:http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html
题目:
A very frequent interview question. Suppose you have a tree, how could you serialize it to file and revert it back? For example,
1
/ \
2 3
\ /
4 5
/ \
6 7
[Thoughts]
一个比较简单直接的做法是,通过前序遍历来做,把所有空节点当做“#”来标示。那么这棵树可以表示为
1
/ \
2 3
/ \ / \
# 4 5 #
/ \
6 7
/ \ / \
# # # #
那么前序遍历的结果就是: {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'}; 代码如下:
参考 http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html
代码:
// Tree serialize
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};
void serialize(TreeNode* root, vector<char> &result) {
if (root == NULL) {
result.push_back('#'); // 表示终结结点
return;
}
result.push_back(root->val + '0');
serialize(root->left, result);
serialize(root->right, result);
}
// de-serialize
TreeNode* deserialize(const vector<char> &num, int &index) {
if (index >= num.size()) {
return NULL;
}
if (num[index] == '#') {
index++;
return NULL;
}
TreeNode *root = new TreeNode(num[index] -'0');
index++;
root->left = Deserialize(num, index);
root->right = Deserialize(num, index);
return root;
}
int main() {
vector<char> numbers = {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'};
int index = 0;
TreeNode* root = deserialize(number, index);
vector<char> res;
serialize(root, res);
return 0;
}
Deserialize Tree的stack解法
EPI 6.8. pg. 236.
Reconstructing A Binary Tree From A Preorder Traversal With Marker. Design an O(n) time algorithm for reconstructing a binary tree from a preorder visit sequence that uses null to mark empty children. How would you modify your reconstruction algorithm if the sequence corresponded to a postorder or inorder walk.
代码:
#define null 0;
TreeNode* reconstruct_preorder(const vector<int>& preorder) {
stack<TreeNode*> s;
// traversal back to forth
for (auto it = preorder.crbegin(); it != preorder.crend(); ++it) {
if (!(*it)) {
s.push(NULL);
} else {
TreeNode* l = s.top(); s.pop();
TreeNode* r = s.top(); s.pop();
TreeNode* root = new TreeNode(*it);
root->left = l;
root->right = r;
s.push(root);
}
}
return s.top();
}
No comments:
Post a Comment