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

austurela 发表于 2014-3-4 07:07
How is this?
Testing:

楼主还有一个，就是每个节点的左孩子和右孩子一定是比它父亲大一或者小1，感觉其实在判断left和right是不是有这个点对应的index的时候只需要用if就可以了，如果能到达这个index，那么说明所有绝对值小于或等于这个index的点已经经历过了

austurela 发表于 2014-3-4 07:07
How is this?
Testing:

层主我问下，你是怎么判断节点在一条线上呢，就比如说root.left.right和root.right.left，因为按图上画的，root.left.right就跟root在一条垂直线上了，这时候root.right.left有节点的话，位置不就跟那个root.left.right重合了么？

austurela 发表于 2014-3-4 07:07
How is this?
Testing:

层主我问下，你是怎么判断节点在一条线上呢，就比如说root.left.right和root.right.left，因为按图上画的，root.left.right就跟root在一条垂直线上了，这时候root.right.left有节点的话，位置不就跟那个root.left.right重合了么？

austurela 发表于 2014-3-4 07:07
How is this?
Testing:

层主我问下，你是怎么判断节点在一条线上呢，就比如说root.left.right和root.right.left，因为按图上画的，root.left.right就跟root在一条垂直线上了，这时候root.right.left有节点的话，位置不就跟那个root.left.right重合了么？

我在疑惑这道题会不会有交叉的情况，如果有较差那就不知道要怎么做了，没有交叉的话那就很好说，中序遍历一下带着列数然后往hash里面存就好了

用level-order遍历然后把相应的点加到arraylist里面去吧

BFS-》 保证顺序，即越靠近根的在队列前面
然后map<vertical_index, queue<node*>>.
其中，根的vertical_index是0，往左减1，往右加一。
用两个变量记录min_vertical_index, max_vertical_index .
打印时从map里，从min_vertical_index, 到 max_vertical_index

这道貌似是高频题啊。

22691482 发表于 2014-11-4 13:03
BFS-》 保证顺序，即越靠近根的在队列前面
然后map.
其中，根的vertical_index是0，往左减1，往右加一。
...

请问BFS如何知道当前节点的vertical_index呢？

我觉得可以用TreeMap，随时保证index按顺序排列，TreeMap<Integer, TreeMap<Integer, Integer>> map;
递归DFS，每次调用传入level以及横向的index，左孩子-1，右孩子+1

1. TreeMap<Integer, TreeMap<Integer, Integer>> map;
   
2. 
   
3.     void verticalPrint(TreeNode root) {
   
4.         if (root == null) return;
   
5.         map = new TreeMap<Integer, TreeMap<Integer, Integer>>();
   
6. 
   
7.         populateMap(root, 1, 0);
   
8.         printMap(map);
   
9.     }
   
10. 
    
11.     void populateMap(TreeNode root, int level, int indent) {
    
12.         if (!map.containsKey(indent)) map.put(indent, new TreeMap<Integer, Integer>());
    
13.         map.get(indent).put(level, root.val);
    
14. 
    
15.         if (root.left != null) {
    
16.             populateMap(root.left, level+1, indent-1);
    
17.         }
    
18.         if (root.right != null) {
    
19.             populateMap(root.right, level+1, indent+1);
    
20.         }
    
21.     }
    
22. 
    
23.     void printMap(TreeMap<Integer, TreeMap<Integer, Integer>> map) {
    
24.         for (Integer indent : map.keySet()) {
    
25.             for (Integer level : map.get(indent).keySet()) {
    
26.                 System.out.print(map.get(indent).get(level) + " ");
    
27.             }
    
28.             System.out.println();
    
29.         }
    
30.     }

复制代码

补充内容 (2014-11-24 08:46):
时间复杂度O(NloglogN)，因为两层TreeMap所以两个log（大家觉得对么？），空间复杂度O(N)