Print Binary Tree Vertically (Medium)
Given a binary tree, print it vertically from left to right according to width.
If nodes are in the same width, print them from top to bottom, if in the same height, print them from left to right
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its vertical order traversal as:
[
[9],
[3,15],
[20],
[7]
]
time complexity of above implementation is O(nLogn).
Java代码：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
void getVerticalOrder(TreeNode root, int hd, TreeMap<Integer, ArrayList> ht) {
// Base case
if (root == null)
return;
// Store current node in map 'm'
if(ht.get(hd)!=null){
ArrayList x = ht.get(hd) ;
x.add(root.val);
ht.put(hd, x);
}else{
ArrayList<Integer> al = new ArrayList<>();
al.add(root.val);
ht.put(hd, al);
}
// Store nodes in left subtree
getVerticalOrder(root.left, hd-1, ht);
// Store nodes in right subtree
getVerticalOrder(root.right, hd+1, ht);
}
void printVerticalOrder(TreeNode root) {
// Create a map and store vertical oder in map using
// function getVerticalOrder()
TreeMap<Integer, ArrayList> ht = new TreeMap<>();
int hd = 0;
getVerticalOrder(root, hd,ht);
// Traverse the map and print nodes at every horigontal
// distance (hd)
Set<Integer> i = ht.keySet();
for(int keys:i){
System.out.println(ht.get(keys));
}
}