LC314. Binary Tree Vertical Order Traversal
Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right.
题目要求从左到右，从上到下一排一排的遍历一棵树。唔，遍历，按层的话bfs用队列，前序中序后序可以递归， dfs用栈，按排遍历，HashTable :D
上面的解析写的真好 思路是利用queue先按层遍历，因为上层的node要先输出。同时求出每一个node的col值，存入map。最后从map出取出来。TreeMap的话可以保证递增的排序，但是get是lg(n), 而hashmap是O(1)的，我忽略了其实cols一定是连续的所以只要记录max, min就可以了。Hashmap要快一些。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
Queue<Integer> cols = new LinkedList<Integer>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
queue.add(root);
cols.add(0);
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
while(!queue.isEmpty()){
TreeNode node = queue.poll();
int col = cols.poll();
min = Math.min(min, col);
max = Math.max(max, col);
if(!map.containsKey(col)) map.put(col, new ArrayList<Integer>());
map.get(col).add(node.val);
if(node.left != null) {
queue.offer(node.left);
cols.offer(col - 1);
}
if(node.right != null){
queue.offer(node.right);
cols.offer(col + 1);
}
} // while
for(int i = min; i <= max; i++){
res.add(map.get(i));
}
return res;
}
}
O(n) with hashmap, O(nlgn) with Treemap
👆Java 集合的各种时间还是要多看看。
其实我还想多看看尧尧❤️…