/*
* 314. Binary Tree Vertical Order Traversal
* 2016-7-5 by Mingyang
* 这是非常有趣的一道题目,一开始就知道用BFS来做,并且知道要两个queue,
* 但是后面在想能不能用更简单的方法来做呢?于是用了一个pre-order的方法来做
* 那么做有一个case过不了,把贴图贴在最后了,附上两种方法的代码
*/
//代码1:用pre-order来做的,好像不行哎
public static HashMap<Integer,List<Integer>> map;
public static List<List<Integer>> verticalOrder(TreeNode root) {
map=new HashMap<Integer,List<Integer>>();
List<List<Integer>> res=new ArrayList<List<Integer>>();
dfs(root,map,0);
List<Integer> sortedKeys=new ArrayList(map.keySet());
Collections.sort(sortedKeys);
for(int a:sortedKeys){
res.add(map.get(a));
}
return res;
}
public static void dfs(TreeNode root, HashMap<Integer,List<Integer>> map,int index){
if(root==null)
return;
if(map.containsKey(index)){
map.get(index).add(root.val);
}else{
map.put(index,new ArrayList<Integer>());
map.get(index).add(root.val);
}
dfs(root.left,map,index-1);
dfs(root.right,map,index+1);
}
//代码2:用BFS
public List<List<Integer>> verticalOrder1(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Map<Integer, ArrayList<Integer>> map = new HashMap<>();
Queue<TreeNode> q = new LinkedList<>();
Queue<Integer> cols = new LinkedList<>();
q.add(root);
cols.add(0);
int min = 0, max = 0;
while(!q.isEmpty()) {
TreeNode node = q.poll();
int col = cols.poll();
if(!map.containsKey(col))
map.put(col, new ArrayList<Integer>());
map.get(col).add(node.val);
if(node.left != null) {
q.add(node.left);
cols.add(col - 1);
//更新最小最大值,好聪明!不用在后面sort map的keys了
if(col <= min) min = col - 1;
}
if(node.right != null) {
q.add(node.right);
cols.add(col + 1);
if(col >= max) max = col + 1;
}
}
for(int i = min; i <= max; i++) {
res.add(map.get(i));
}
return res;
}