Facebook Phone Interview

22691482 发表于 2014-11-8 15:20
Onsite据说一天就回复了。。祝好运啊！

明天是周六啊。。。多谢多谢你也好运！

有两个方法，不知道哪个好一些
1. 在构造函数里，获得树的最小节点。hasNext return 当前节点是否为空, next则返回当前节点并且重新计算当前节点为当前节点的successor。
2. 构造一个链表

我用c++实现了一个，大家看看有么有bug吧。。

1. #include <iostream>
   
2. #include <stack>
   
3. using namespace std;
   
4. 
   
5. struct Tree{
   
6.     int val;
   
7.     Tree *left, *right;
   
8.     Tree(int mval):val(mval), left(NULL), right(NULL){}
   
9. };
   
10. 
    
11. class TreeIterator{
    
12. public:
    
13.     TreeIterator(Tree *root){
    
14.         flag = true;
    
15.         if(root == NULL){
    
16.             cur = NULL;
    
17.             cout<<"invalid root point"<<endl;
    
18.         }else{
    
19.             while(root){
    
20.                 st.push(root);
    
21.                 root = root->left;
    
22.             }
    
23.             cur = st.top();
    
24.         }
    
25.     }
    
26.     int value(){
    
27.         if(cur == NULL){
    
28.             cout<<"invalid operation"<<endl;
    
29.             return -1;
    
30.         }else{
    
31.             cout<<cur->val<<endl;
    
32.             return cur->val;
    
33.         }
    
34.     }
    
35.     void next(){
    
36.         if(cur == NULL){
    
37.             cout<<"No next point"<<endl;
    
38.             return;
    
39.         }else{
    
40.             if(cur->right){
    
41.                 st.pop();
    
42.                 cur = cur->right;
    
43.                 st.push(cur);
    
44.                 while(cur->left){
    
45.                     cur = cur->left;
    
46.                     st.push(cur);
    
47.                 }
    
48.             }else{
    
49.                 st.pop();
    
50.                 cur = st.empty()?NULL:st.top();
    
51.             }
    
52.         }
    
53.     }
    
54.     bool hasNext(){
    
55.         return cur != NULL;
    
56.     }
    
57. private:
    
58.     stack<Tree* > st;
    
59.     Tree* cur;
    
60.     bool flag;
    
61. };
    
62. 
    
63. int main(){
    
64.     Tree *t1 = new Tree(1);
    
65.     Tree *t2 = new Tree(2);
    
66.     Tree *t3 = new Tree(3);
    
67.     Tree *t4 = new Tree(4);
    
68.     Tree *t5 = new Tree(5);
    
69.     Tree *t6 = new Tree(6);
    
70.     Tree *t7 = new Tree(7);
    
71.     t1->left = t2, t1->right = t3;
    
72.     t2->left = t4, t2->right = t5;
    
73.     t3->left = t6, t3->right = t7;
    
74.     TreeIterator tit(t1);
    
75.     while(tit.hasNext()){
    
76.         tit.value();
    
77.         tit.next();
    
78.     }
    
79. }
    
80. 
    
81. /*
    
82.                 1
    
83.                /\
    
84.               2 3
    
85.              /\ /\
    
86.             4 56 7
    
87.             */
    

复制代码

写树的iterator，这道题我给我同学mock interview的时候就考了一下