Problem:
Binary Tree Vertical Order TraversalGiven 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.
Examples 1:
Input: [3,9,20,null,null,15,7]
3
/\
/ \
9 20
/\
/ \
15 7
Output:
[
[9],
[3,15],
[20],
[7]
]
Examples 2:
Input: [3,9,8,4,0,1,7]
3
/\
/ \
9 8
/\ /\
/ \/ \
4 01 7
Output:
[
[4],
[9],
[3,0,1],
[8],
[7]
]
Solution
The node in the same array has the same distance from the middle line, so we can traversal the tree, count the distance from the middle line, when we reaches the leaf, we add the node into a map, the key is the distance from middle line, the value is the array contains this node. We need to traversal the tree, the cost is O(N), we need a map to store the tree nodes, the space cost is O(N). If order of the array does matter, we need to use TreeMap instead of HashMap, insertion of the Nth element cost O(MlogM), M is the total number of columns, so the time cost is still dominated by O(N).
import java.util.*;
public class BSTVerticalOrder {
Map<Integer, List<Node>> result = new TreeMap<>();
/*
3
/\
/ \
9 8
/\ /\
/ \/ \
4 01 7
*/
//result: 2-[4];0-[0,1,3];1-[9];-2[7];-1[8];
public void verticalOrder(Node root, int leftCount) {//3,0; 9,1; 4,2; 0,0;8,-1;1,0;7,-2
if(root == null) return;
if(root.left == null && root.right == null) {
addResult(leftCount, root);
return;
}
verticalOrder(root.left, leftCount+1);
verticalOrder(root.right, leftCount-1);
addResult(leftCount, root);
}
private void addResult(int leftCount, Node root) {
List<Node> column = result.get(leftCount);
if(column == null) {
column = new ArrayList<>();
column.add(root);
result.put(leftCount, column);
} else {
column.add(root);
}
}
public static void main(String...args) {
BSTVerticalOrder bstVO = new BSTVerticalOrder();
Node root = new Node(3, new Node(9, new Node(4, null, null), new Node(0, null, null)),
new Node(8, new Node(1, null, null), new Node(7, null, null)));
bstVO.verticalOrder(root, 0);
for(List<Node> column : bstVO.result.values()) {
column.forEach(i -> System.out.print(" " + i.value));
System.out.println();
}
}
private static class Node {
private int value;
private Node left;
private Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
Time cost O(N), space cost O(N).
