fb intern面经，面对奇葩问题膝盖碎了

已跪，45分钟面了道很奇葩的问题，面试是个三哥，有气无力地听着，最后也装模作样回答一些问题.. 跪了
问题：
Print arbitrary binary tree by vertical levels / columns from left to right


example tree

      a
     / \
    b   c
   / \   \
  d   g   z

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

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

不是可以把<key, string>这样存

补充内容 (2014-3-4 06:02):
因为他要求的只是打印出来，不需要有data structure可以存所有的nodes.. 这样可以达到题目要求，可是总觉得不是很好，有点投机取巧，求大大们解释

这个题在做雅虎笔试的时候遇到过，我当时看成求层序遍历了，以为好简单。。用preorder递归应该是不行的，举个反例，假设第一个左孩子的右子树往右延伸了很长，那么在bfs他们都会在跟的右子树之前被加入到hash表，这是不对的。用层序遍历其实也不复杂，用个pair把他再水平方向的偏移量记录一下即可。贴一下我的实现，例子是楼主给出的那个。大家看看有没有bug。

1. #include <iostream>
   
2. #include <map>
   
3. #include <string>
   
4. #include <queue>
   
5. #include <vector>
   
6. using namespace std;
   
7. 
   
8. struct tree{
   
9.     string key;
   
10.     tree *left, *right;
    
11.     tree(string mkey):key(mkey), left(NULL), right(NULL){}
    
12. };
    
13. 
    
14. typedef pair<tree*, int> pti;
    
15. 
    
16. map<int, vector<tree*> > dict;
    
17. 
    
18. void build(tree *root){
    
19.     if(root == NULL){
    
20.         return;
    
21.     }
    
22.     queue<pti> que;
    
23.     que.push(pti(root, 0));
    
24.     while(!que.empty()){
    
25.         pti cur = que.front();
    
26.         que.pop();
    
27.         dict[cur.second].push_back(cur.first);
    
28.         if(cur.first->left){
    
29.             que.push(pti(cur.first->left, cur.second-1));
    
30.         }
    
31.         if(cur.first->right){
    
32.             que.push(pti(cur.first->right, cur.second+1));
    
33.         }
    
34.     }
    
35. }
    
36. 
    
37. void solve(tree *root){
    
38.     if(root == NULL){
    
39.         return;
    
40.     }
    
41.     build(root);
    
42.     map<int, vector<tree*> >::const_iterator it = dict.begin();
    
43.     while(it != dict.end()){
    
44.         vector<tree*>::const_iterator itt = it->second.begin();
    
45.         while(itt != it->second.end()){
    
46.             cout<<(*itt)->key<<"\t";
    
47.             ++itt;
    
48.         }
    
49.         cout<<endl;
    
50.         ++it;
    
51.     }
    
52. }
    
53. 
    
54. int main(){
    
55.     tree *t1 = new tree("a");
    
56.     tree *t2 = new tree("b");
    
57.     tree *t3 = new tree("c");
    
58.     tree *t4 = new tree("d");
    
59.     tree *t5 = new tree("e");
    
60.     tree *t6 = new tree("g");
    
61.     tree *t7 = new tree("z");
    
62.     tree *t8 = new tree("i");
    
63.     tree *t9 = new tree("q");
    
64.     tree *t10 = new tree("x");
    
65.     tree *t11 = new tree("x1");
    
66.     tree *t12 = new tree("x2");
    
67.     t1->left = t2;
    
68.     t1->right = t3;
    
69.     t2->left = t4;
    
70.     t2->right = t6;
    
71.     t4->right = t5;
    
72.     t3->right = t7;
    
73.     t7->left = t8;
    
74.     t8->left = t9;
    
75.     t9->left = t10;
    
76.     t10->left = t11;
    
77.     t11->left = t12;
    
78.     solve(t1);
    
79. }
    
80. 
    
81. /*
    
82.       a
    
83.      / \
    
84.     b   c
    
85.    / \   \
    
86.   d   g   z
    
87.    \     /
    
88.     e   i
    
89.        /
    
90.       q
    
91.      /
    
92.     x
    
93.    /
    
94.   x1
    
95. /
    
96. x2
    
97. */
    
98. 
    

复制代码

我的想法是用hashmap， key是列的偏移，设定root偏移为0，然后向左走偏移-1，向右偏移+1，value是一个String的arraylist。然后应该和lz想法就差不多了，preorder遍历，每个node的值append到对应的偏移的arraylist后面

这题虽然略蛋疼但还比较容易，preorder traversal tree，用unordered_map<int,  vector<TreeNode*> >来保存每个key相同的结点集合，根的key是0，左树加1， 右树减1。 key是正是负都无所谓

How is this?

1. import java.util.ArrayList;
   
2. 
   
3. public class PrintByColumn<T> {
   
4.        
   
5.         public void Print(TreeNode<T> root){
   
6.                 ArrayList<ArrayList<T>> right = new ArrayList<ArrayList<T>>();
   
7.                 ArrayList<ArrayList<T>> left = new ArrayList<ArrayList<T>>();
   
8.                 printHelper(0, root, left, right);
   
9.                 // Print result
   
10.                 for(int i = left.size() - 1; i > 0; i--){
    
11.                         System.out.println(left.get(i));
    
12.                 }
    
13.                 for(int i = 0; i < right.size(); i++){
    
14.                         System.out.println(right.get(i));
    
15.                 }
    
16.         }
    
17.        
    
18.         private void printHelper(int index, TreeNode<T> root, ArrayList<ArrayList<T>> left, ArrayList<ArrayList<T>> right){
    
19.                 // Base case
    
20.                 if(root == null)        return;
    
21.                 // Normal case
    
22.                 if(index >= 0){
    
23.                         while(right.size() <= index){
    
24.                                 right.add(new ArrayList<T>());
    
25.                         }
    
26.                         right.get(index).add(root.data);
    
27.                 }
    
28.                 else{
    
29.                         while(left.size() <= -index){
    
30.                                 left.add(new ArrayList<T>());
    
31.                         }
    
32.                         left.get(-index).add(root.data);
    
33.                 }
    
34.                 // Recurse
    
35.                 printHelper(index - 1, root.left, left, right);
    
36.                 printHelper(index + 1, root.right, left, right);
    
37.         }
    
38. }
    

复制代码

Testing:

1. import java.util.*;
   
2. 
   
3. class TreeNode<T>{
   
4.         TreeNode<T> left;
   
5.         TreeNode<T> right;
   
6.         T data;
   
7.        
   
8.         TreeNode(T data){
   
9.                 this.data = data;
   
10.         }
    
11. }
    
12. 
    
13. public class Test {
    
14.         public static void main(String[] args){
    
15.                 TreeNode<String> root = new TreeNode<String>("a");
    
16.                 root.left = new TreeNode<String>("b");
    
17.                 root.right = new TreeNode<String>("c");
    
18.                
    
19.                 root.left.left = new TreeNode<String>("d");
    
20.                 root.left.right = new TreeNode<String>("g");
    
21.                
    
22.                 root.right.right = new TreeNode<String>("z");
    
23.                 root.right.right.left = new TreeNode<String>("i");
    
24.                 root.right.right.left.left = new TreeNode<String>("q");
    
25.                 root.right.right.left.left.left = new TreeNode<String>("x");
    
26.                 root.right.right.left.left.left.left = new TreeNode<String>("x1");
    
27.                 root.right.right.left.left.left.left.left = new TreeNode<String>("x2");
    
28.                
    
29.                 root.left.left.right = new TreeNode<String>("e");
    
30.                
    
31.                 PrintByColumn<String> test = new PrintByColumn<String>();
    
32.                 test.Print(root);
    
33.         }
    
34. }
    

复制代码

补充内容 (2014-3-4 07:08):
Output:
[x2]
[d, x1]
[b, e, x]
[a, g, q]
[c, i]
[z]

跟求bs的最大深度一样 用recursion求完深度以后加到深度的arraylist即可

补充内容 (2014-3-4 09:32):
貌似不对 还得想想

补充内容 (2014-3-4 09:45):
我的做法跟lz 一样 左面key减1右面key加1 然后用hashmap 保存 key linkedlist 和最大最小值 然后iterate

弄个链表不行吗。正的往右，负的往左。
或者弄俩数组，一个存正的，一个存负的。

当年也正派 发表于 2014-3-4 09:45
我的想法是用hashmap， key是列的偏移，设定root偏移为0，然后向左走偏移-1，向右偏移+1，value是一个Strin ...

我觉得也是，HashMap<Integer,ArrayList<TreeNode>>用来保存对应的key对应的节点，更新最小key value就行了。然后iterate hashmap，比如key的最小是-5，那么说明root左边有5层，那么key=-5 to key not in HashMap，依次print HashMap中的ArrayList

想法差不多，BFS。 HashMap<Integer, ArrayList<Integer>> , 存一下最大最小列数
=========
key   value
0      a -> g -> q
-1      b -> e -> x
1      c -> i
-2      d -> x1
2      z
-3      x2

用vector<vector<Node*>> tree_list 结构是可以存的。做一个pre-order traverse，把node放到相应的level中，因为是pre-order，所以tree_list.size()始终等于 depth 或 depth + 1。

lingeast 发表于 2014-3-5 11:50
用vector tree_list 结构是可以存的。做一个pre-order traverse，把node放到相应的level中，因为是pre-orde ...

pre-ordery 应该不行把，因为会把level的顺序弄乱。
虽然题主给的case这题可以用Pre-order，但我觉得是特例。
得 Breadth first search。