## Saturday, December 5, 2015

### LeetCode 314 Binary Tree Vertical Order Traversal

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]
]```
https://discuss.leetcode.com/topic/31954/5ms-java-clean-solution
The following solution takes `5ms`.
• BFS, put `node``col` into queue at the same time
• Every left child access `col - 1` while right child `col + 1`
• This maps `node` into different `col` buckets
• Get `col` boundary `min` and `max` on the fly
• Retrieve `result` from `cols`
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<>();

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>());
}

if (node.left != null) {
min = Math.min(min, col - 1);
}

if (node.right != null) {
max = Math.max(max, col + 1);
}
}

for (int i = min; i <= max; i++) {
}

return res;
}``````
Alternatively, we can calculate the rang first, then insert into buckets.
https://discuss.leetcode.com/topic/33411/3ms-java-solution-beats-100
There is no difference when using HashMap. Since by using HashMap it need keep track of min and max as well, I'd rather directly insert into list by computing min and max in advance.
``````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++) {
}

Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> colQueue = new LinkedList<>();

while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int col = colQueue.poll();

if (node.left != null) {
}
if (node.right != null) {
}
}

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);
}``````
https://leetcode.com/discuss/73113/using-hashmap-bfs-java-solution
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>());

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://leetcode.com/discuss/79821/java-bfs-concise-code-using-2-maps

```    public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
HashMap<TreeNode, Integer> map1 = new HashMap<TreeNode, Integer>();
TreeMap<Integer, List<Integer>> map2 = new TreeMap<Integer, List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
map1.put(root, 0);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
int index = map1.get(node);
List<Integer> list = map2.containsKey(index) ? map2.get(index) : new ArrayList<Integer>();
map2.put(index, list);
if (node.left != null) {
queue.offer(node.left);
map1.put(node.left, index - 1);
}
if (node.right != null) {
queue.offer(node.right);
map1.put(node.right, index + 1);
}
}
}
Iterator<Integer> it = map2.keySet().iterator();
while (it.hasNext()) {
}
return result;
}
}```
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>());
}

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);
}
}```
https://leetcode.com/discuss/77236/just-to-be-different-java-4-5-ms-95%25-dfs-solution
1. First I traverse the tree and determine the min, max indices as well as the depth of the tree.
2. 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).
3. The length of the array columns is determined by the depth (I call it 'height') of the tree.
4. 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.
5. 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++) {
for (int j = 0; j < tree[0].length; j++) {
if (!tree[i][j].isEmpty()) {
}
}
}
return res;
}

private void order(TreeNode root, int level, int l, int height, ArrayList<Integer>[][] tree) {
if (root == null) return;
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);
}
``````
https://leetcode.com/discuss/73108/level-order-traversal-wrapping-nodes-with-a-shift-index