https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
http://www.cnblogs.com/EdwardLiu/p/5093131.html
X. Level Order Traversal
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/314_Binary_Tree_Vertical_Order_Traversal.java
https://www.geeksforgeeks.org/print-a-binary-tree-in-vertical-order-set-3-using-level-order-traversal/
https://discuss.leetcode.com/topic/33411/3ms-java-solution-beats-100
Only need track min, not max level.
public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } //map's key is column, we assume the root column is zero, the left node will minus 1 ,and the right node will plus 1 HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); Queue<TreeNode> queue = new LinkedList<>(); //use a HashMap to store the TreeNode and the according cloumn value HashMap<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>(); queue.offer(root); weight.put(root, 0); int min = 0; while (!queue.isEmpty()) { TreeNode node = queue.poll(); int w = weight.get(node); if (!map.containsKey(w)) { map.put(w, new ArrayList<>()); } map.get(w).add(node.val); if (node.left != null) { queue.add(node.left); weight.put(node.left, w - 1); } if (node.right != null) { queue.add(node.right); weight.put(node.right, w + 1); } //update min ,min means the minimum column value, which is the left most node min = Math.min(min, w); } while (map.containsKey(min)) { res.add(map.get(min++)); } return res; }
X. TreeMap
https://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/
http://www.itdadao.com/article/48930/
https://leetcode.com/discuss/79821/java-bfs-concise-code-using-2-maps
用了treemap来维护左右关系，其实也可以不用，记录一个min的index就好。
X. DFS
http://www.zrzahid.com/vertical-and-zigzag-traversal-of-binary-tree/
https://leetcode.com/discuss/77236/just-to-be-different-java-4-5-ms-95%25-dfs-solution
https://leetcode.com/discuss/73108/level-order-traversal-wrapping-nodes-with-a-shift-index
http://www.cnblogs.com/EdwardLiu/p/5093131.html
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. Given binary tree [3,9,20,4,5,2,7], _3_ / \ 9 20 / \ / \ 4 5 2 7 return its vertical order traversal as: [ [4], [9], [3,5,2], [20], [7] ]
X. Level Order Traversal
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/314_Binary_Tree_Vertical_Order_Traversal.java
private class QueueNode {
public TreeNode node;
public int depth;
public QueueNode(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
if (root == null) return Collections.emptyList();
Queue<QueueNode> queue = new LinkedList<>();
Map<Integer, List<Integer>> map = new HashMap<>();
queue.add(new QueueNode(root, 0));
int min = 0, max = 0;
while (!queue.isEmpty()) {
TreeNode cur = queue.peek().node;
int depth = queue.poll().depth;
if (!map.containsKey(depth))
map.put(depth, new ArrayList<>());
map.get(depth).add(cur.val);
min = Math.min(min, depth);
max = Math.max(max, depth);
if (cur.left != null)
queue.add(new QueueNode(cur.left, depth - 1));
if (cur.right != null)
queue.add(new QueueNode(cur.right, depth + 1));
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = min; i <= max; i ++)
ans.add(map.get(i));
return ans;
}
If we use level order traversal, we can make sure that if a node like 12 comes below in same vertical line, it is printed after a node like 9 which comes above in vertical line.
1. To maintain a hash for the branch of each node.
2. Traverse the tree in level order fashion.
3. In level order traversal, maintain a queue
which holds, node and its vertical branch.
* pop from queue.
* add this node's data in vector corresponding
to its branch in the hash.
* if this node hash left child, insert in the
queue, left with branch - 1.
* if this node hash right child, insert in the
queue, right with branch + 1
https://discuss.leetcode.com/topic/31954/5ms-java-clean-solution
The following solution takes
5ms.- BFS, put
node,colinto queue at the same time - Every left child access
col - 1while right childcol + 1 - This maps
nodeinto differentcolbuckets - Get
colboundaryminandmaxon the fly - Retrieve
resultfromcols
Note that
TreeMap version takes 9ms.
Here is an example of
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]. Notice that every child access changes one column bucket id. So 12 actually goes ahead of 11.public List<List<Integer>> verticalOrder(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;
int 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);
min = Math.min(min, col - 1);
}
if (node.right != null) {
q.add(node.right);
cols.add(col + 1);
max = Math.max(max, col + 1);
}
}
for (int i = min; i <= max; i++) {
res.add(map.get(i));
}
return res;
}https://discuss.leetcode.com/topic/33411/3ms-java-solution-beats-100
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> cols = new ArrayList<>();
if (root == null) {
return cols;
}
int[] range = new int[] {0, 0};
getRange(root, range, 0);
for (int i = range[0]; i <= range[1]; i++) {
cols.add(new ArrayList<Integer>());
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> colQueue = new LinkedList<>();
queue.add(root);
colQueue.add(-range[0]);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int col = colQueue.poll();
cols.get(col).add(node.val);
if (node.left != null) {
queue.add(node.left);
colQueue.add(col - 1);
}
if (node.right != null) {
queue.add(node.right);
colQueue.add(col + 1);
}
}
return cols;
}
public void getRange(TreeNode root, int[] range, int col) {
if (root == null) {
return;
}
range[0] = Math.min(range[0], col);
range[1] = Math.max(range[1], col);
getRange(root.left, range, col - 1);
getRange(root.right, range, col + 1);
}Only need track min, not max level.
public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } //map's key is column, we assume the root column is zero, the left node will minus 1 ,and the right node will plus 1 HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); Queue<TreeNode> queue = new LinkedList<>(); //use a HashMap to store the TreeNode and the according cloumn value HashMap<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>(); queue.offer(root); weight.put(root, 0); int min = 0; while (!queue.isEmpty()) { TreeNode node = queue.poll(); int w = weight.get(node); if (!map.containsKey(w)) { map.put(w, new ArrayList<>()); } map.get(w).add(node.val); if (node.left != null) { queue.add(node.left); weight.put(node.left, w - 1); } if (node.right != null) { queue.add(node.right); weight.put(node.right, w + 1); } //update min ,min means the minimum column value, which is the left most node min = Math.min(min, w); } while (map.containsKey(min)) { res.add(map.get(min++)); } return res; }
public int index = 0; public TreeMap<Integer, List<Integer>> tm; public class Pair { TreeNode node; int index; public Pair(TreeNode n, int i) { node = n; index = i; } } public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); tm = new TreeMap<Integer, List<Integer>>(); if (root == null) return res; Queue<Pair> q = new LinkedList<Pair>(); q.offer(new Pair(root, 0)); while (!q.isEmpty()) { Pair cur = q.poll(); if (!tm.containsKey(cur.index)) tm.put(cur.index, new ArrayList<Integer>()); tm.get(cur.index).add(cur.node.val); if (cur.node.left != null) q.offer(new Pair(cur.node.left, cur.index-1)); if (cur.node.right != null) q.offer(new Pair(cur.node.right, cur.index+1)); } for (int key : tm.keySet()) res.add(tm.get(key)); return res; }
https://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/
The above solution uses preorder traversal and Hashmap to store nodes according to horizontal distances. Since above approach uses preorder traversal, nodes in a vertical line may not be prined in same order as they appear in tree. For example, the above solution prints 12 before 9 in below tree. See this for a sample run.
https://leetcode.com/discuss/79821/java-bfs-concise-code-using-2-maps
用了treemap来维护左右关系，其实也可以不用，记录一个min的index就好。
X. DFS
http://www.zrzahid.com/vertical-and-zigzag-traversal-of-binary-tree/
public static void verticalTrversal(BTNode root){ int[] minmax = new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE}; Map<Integer, ArrayList<BTNode>> verticals = new HashMap<Integer, ArrayList<BTNode>>(); traverse(root, verticals, 0, minmax); for(int i = minmax[0]; i<=minmax[1]; i++){ if(verticals.containsKey(i)){ for(BTNode vnode : verticals.get(i)){ System.out.print(vnode.key+","); } System.out.println(); } } } private static void traverse(BTNode node, Map<Integer, ArrayList<BTNode>> verticals, int score, int[] minmax){ if(!verticals.containsKey(score)){ verticals.put(score, new ArrayList<BTNode>()); } verticals.get(score).add(node); minmax[0] = Math.min(minmax[0], score); minmax[1] = Math.max(minmax[1], score); if(node.left != null){ traverse(node.left, verticals, score-1, minmax); } if(node.right != null){ traverse(node.right, verticals, score+1, minmax); } }
- First I traverse the tree and determine the min, max indices as well as the depth of the tree.
- I use these limits to construct a 2D array of size (max index - min index + 1). e.g. if min index = -2, and max index = 3, then the length of the array rows is 3 + 2 + 1(root).
- The length of the array columns is determined by the depth (I call it 'height') of the tree.
- I then create an empty ArrayList in each cell of our 2D array to handle the collisions. Note that I preallocate 2 slots of capacity for each ArrayList, since we can have at most 2 nodes competing for the same cell.
- Now that all the memory is preallocated I traverse the tree the second time and fill in the cells of the 2D array. Note that some of the cells will contain empty arrayLists in the end, so this is not the most space efficient method.
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
int[] minmax = new int[3];
getEnds(root, 0, 1, minmax);
ArrayList<Integer>[][] tree = new ArrayList[minmax[1] - minmax[0] + 1][minmax[2]];
for (int i = 0; i < tree.length; i++)
for (int j = 0; j < tree[0].length; j++)
tree[i][j] = new ArrayList<Integer>(2);
order(root, 0, -minmax[0], 0, tree);
for (int i = 0; i < tree.length; i++) {
res.add(new ArrayList<Integer>());
for (int j = 0; j < tree[0].length; j++) {
if (!tree[i][j].isEmpty()) {
res.get(i).addAll(tree[i][j]);
}
}
}
return res;
}
private void order(TreeNode root, int level, int l, int height, ArrayList<Integer>[][] tree) {
if (root == null) return;
tree[l + level][height].add(root.val);
order(root.left, level-1, l, height + 1, tree);
order(root.right, level+1, l, height + 1, tree);
}
private void getEnds(TreeNode root, int level, int height, int[] minmax) {
if (root == null) return;
minmax[0] = Math.min(level, minmax[0]);
minmax[1] = Math.max(level, minmax[1]);
minmax[2] = Math.max(height, minmax[2]);
getEnds(root.left, level-1, height + 1, minmax);
getEnds(root.right, level+1, height + 1, minmax);
}
