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

这个题在做雅虎笔试的时候遇到过，我当时看成求层序遍历了，以为好简单。。用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. 
    

复制代码

your output is like this omg!

x2       
d        x1       
b        e        x       
a        g        q       
c        i       
z       

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

preorder是不行，会打乱顺序，必须得BFS

kongweihan 发表于 2014-11-24 08:41
请问BFS如何知道当前节点的vertical_index呢？

用一个map存偏移量，Map<TreeNode, Integer>

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

A solution:  find the leftmost and rightmost level first. Then print each level using recursion.

        public static void main(String[] args) {
                int[] min = new int[1];
                getLeftmostIndex(a, 0, min);
               
                int[] max = new int[1];
                getRightmostIndex(a, 0, max);
               
                for (int level = min[0]; level <= max[0]; ++level) {
                        List<Integer> list = new ArrayList<Integer>();
                        getOneLevel(a, 0, level, list);
                        System.out.println(list);
                }
        }
       
        public static void getLeftmostIndex(TreeNode root, int curIndex, int[] min) {
                if (root == null) return;
                min[0] = Math.min(min[0], curIndex);
                getLeftmostIndex(root.left, curIndex - 1, min);
                getLeftmostIndex(root.right, curIndex + 1, min);
        }
       
        public static void getRightmostIndex(TreeNode root, int curIndex, int[] max) {
                if (root == null) return;
                max[0] = Math.max(max[0], curIndex);
                getRightmostIndex(root.left, curIndex - 1, max);
                getRightmostIndex(root.right, curIndex + 1, max);               
        }
       
        public static void getOneLevel(TreeNode root, int cur,  int level, List<Integer> list) {
                if (root == null) return;
                if (cur == level) list.add(root.val);
                getOneLevel(root.left, cur - 1, level, list);
                getOneLevel(root.right, cur + 1, level, list);       
        }

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

1. import java.util.*;
   
2. public class Solution {
   
3.     Map<Integer, List<String>> map = new TreeMap<Integer, List<String>>();
   
4.     public List<List<String>> verticalPrint(Tree root) {
   
5.         List<List<String>> result = new ArrayList<List<String>>();
   
6.         if (root != null) radd(root, 0);
   
7.         for (int i : map.keySet()) result.add(map.get(i));
   
8.         return result;
   
9.     }
   
10. 
    
11.     public void radd(Tree root, int x) {
    
12.         if (map.containsKey(x)) map.get(x).add(root.key);
    
13.         else {
    
14.             List<String> tmp = new ArrayList<>();
    
15.             tmp.add(root.key);
    
16.             map.put(x, tmp);
    
17.         }
    
18.         if (root.left  != null) radd(root.left, x-1);
    
19.         if (root.right != null) radd(root.right, x+1);
    
20.     }
    
21. }

复制代码

Neal_kks 发表于 2014-11-25 14:50
这个题在做雅虎笔试的时候遇到过，我当时看成求层序遍历了，以为好简单。。用preorder递归应该是不行的，举 ...

dict 里的 vector<Tree*> 应该初始化一下吧？

Neal_kks 发表于 2014-11-25 14:50
这个题在做雅虎笔试的时候遇到过，我当时看成求层序遍历了，以为好简单。。用preorder递归应该是不行的，举 ...

赞，看起来挺奇葩的题，想通了也挺常规，关键是不要怕

这题最naive的方法应该是traverse, 给每个node有设置对应的vertical level, E.g. root = 0, root.left = -1. root.right = 1.

补充内容 (2015-9-28 03:59):
然后另外维护一个treemap<int, node>, 从vertical level 映射到node。最后讲treemap按vertical level从小到大，按顺序输出

补充内容 (2015-9-28 04:03):
其实也不需要treemap, 直接用hashmapc存即可，只是需要记录vertical index的范围