烧烤节脸书面经 估计跪

因为住的离campus很近，所以电面这一轮就让我去onsite面了。还是45分钟，只不过是面对面，白板编程而已。
题目很简单，Binary Tree Post Order

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

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

结果白板上不能轻易地修改代码，写错了的话就会越来越慌乱。这次吃了亏，以后得好好练习练习。

指针那个解法我还没开始练习，我是偷懒的方法，child打印之后把child pointer给cut掉，估计面试时候会被challenge.准备踏踏实实写一遍lz的解法了。

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

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

楼主是被要求要o(1) 的space 做吗? o(1) space 要怎么做阿

用一个指针记录之前输出的那个节点

这个是怎么做啊？

BillSky 发表于 2017-2-15 23:58
用一个指针记录之前输出的那个节点

这个是怎么做啊？

1. struct TreeNode {
   
2.     TreeNode(int x): val(x), left(NULL), right(NULL) { }
   
3.     int val;
   
4.     TreeNode *left, *right;
   
5. };
   
6. 
   
7. class Solution {
   
8. public:
   
9.     vector<int> postOrderTraversal(TreeNode *root) {
   
10.         vector<int> res;
    
11.         if (root == NULL)
    
12.             return res;
    
13. 
    
14.         stack<TreeNode*> stack;
    
15.         TreeNode *run = root;
    
16.         stack.push(run);
    
17. 
    
18.         while (!stack.empty()) {
    
19.             // push root of each subtree to stack twice
    
20.             // first traverse all left nodes
    
21.             while (run != NULL) {
    
22.                 stack.push(run);
    
23.                 run = run->left;
    
24.             }
    
25. 
    
26.             TreeNode *prev = NULL;
    
27.             run = stack.top();
    
28.             stack.pop();
    
29. 
    
30.             while (!stack.empty()) {
    
31.                 if (run->right == prev) {
    
32.                     // right is visited, run can be print
    
33.                     res.push_back(run->val);
    
34.                     prev = run;
    
35.                     run = stack.top();
    
36.                     stack.pop();
    
37.                 } else {
    
38.                     // deal with the right subtree
    
39.                     stack.push(run);
    
40.                     run = run->right;
    
41.                     break;
    
42.                 }
    
43.             }
    
44.         }
    
45. 
    
46.         return res;
    
47.     }
    
48. };
    

复制代码

Zhenying 发表于 2017-2-16 13:37

这个stack push 的过程 因该就不是o(1) space 了吧?

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

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

Zhenying 发表于 2017-2-17 16:01
这个用stack的算法不是O(1)。面试官没让我用O(1)的做。他只是在我每次写完一个算法后，问我能不能有个更 ...

谢楼主...