脸书电面 9/8

1. LC297 serialize/deserialize BST 与原题不一样的是输出是vector<int>，not a string。
2. LC133 Clone Graph 与原题不一样的是输入不是一个Node *, 而是vector<Node*>， 需要clone这个vector里的所有 nodes。
问面试官所有的nodes 是否fu

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

道会不会有onsite。。。

serialize & deserialize binary binary tree 可以记low_bound 和up_bound, 这样可以省一点空间，不用存 null 节点。 我觉得问BST而不是BT的意图是这个？

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. using namespace std;
   
5. struct TreeNode{
   
6.     int val;
   
7.     TreeNode *left, *right;
   
8.     TreeNode(int val_) {
   
9.         val = val_;
   
10.         left = right = nullptr;
    
11.     }
    
12. };
    
13. 
    
14. void serial(TreeNode* root, vector<int>& ans) {
    
15.     if(!root) return;
    
16.     ans.push_back(root->val);
    
17.     serial(root->left, ans);
    
18.     serial(root->right, ans);
    
19. }
    
20. 
    
21. vector<int> serialize(TreeNode* root){
    
22.     vector<int> ans;
    
23.     serial(root, ans);
    
24.     return ans;
    
25. }
    
26. 
    
27. TreeNode* deserial(vector<int>& nums, int& pos, int lb, int ub) {
    
28.     if(pos == nums.size() || nums[pos] < lb || nums[pos] > ub) return nullptr;
    
29.     int val = nums[pos++];
    
30.     TreeNode* node = new TreeNode(val);
    
31.     node->left = deserial(nums, pos, lb, val-1);
    
32.     node->right = deserial(nums, pos, val+1, ub);
    
33.     return node;
    
34. }
    
35. 
    
36. TreeNode* deserialize(vector<int>& nums) {
    
37.     int pos = 0;
    
38.     return deserial(nums, pos, INT_MIN, INT_MAX);
    
39. }
    
40. 
    
41. int main(int argc, const char * argv[]) {
    
42.     // insert code here...
    
43.     /*       2
    
44.            /   \
    
45.          0       5
    
46.           \    /   \
    
47.            1  4     6
    
48.              /     / \
    
49.             3     7   8
    
50.     */
    
51.     TreeNode n0(0), n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7), n8(8);
    
52.     n2.left = &n0;
    
53.     n2.right = &n5;
    
54.     n0.right = &n1;
    
55.     n5.left = &n4;
    
56.     n5.right = &n6;
    
57.     n4.left = &n3;
    
58.     n6.left = &n7;
    
59.     n6.right = &n8;
    
60.     auto ans = serialize(&n2);
    
61.     auto root = deserialize(ans);
    
62.     queue<TreeNode*> q;
    
63.     q.push(root);
    
64.     while(!q.empty()) {
    
65.         int qsize = q.size();
    
66.         while(qsize-- > 0) {
    
67.             auto top = q.front();
    
68.             q.pop();
    
69.             cout << top->val << " ";
    
70.             if(top->left) q.push(top->left);
    
71.             if(top->right) q.push(top->right);
    
72.         }
    
73.         cout << endl;
    
74.     }
    
75.     return 0;
    
76. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. 如何处理空节点？

多谢!

danielman97 发表于 2017-9-11 03:55
1. 如何处理空节点？

多谢!

用 -1 表示，假设所有节点val 都是正数

楼主是full time 还是 intern

pinteson 发表于 2017-9-11 04:35
用 -1 表示，假设所有节点val 都是正数

java的list可以直接add null

pinteson 发表于 2017-9-11 04:35
用 -1 表示，假设所有节点val 都是正数

traverse 的时候判断一下是否null 不就完了吗? 为啥要特别处理

求问楼主出结果了没