314. Binary Tree Vertical Order Traversal
BFS + HashMap
Time = O(n), space = O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// HashMap key: Horizontal distance; value: Node
class Node {
TreeNode treeNode;
int hd;
public Node(TreeNode treeNode, int hd) {
this.treeNode = treeNode;
this.hd = hd;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Map<Integer, List<Integer>> map = new HashMap<>();
int minHd = 0;
int maxHd = 0;
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(root, 0));
while (!queue.isEmpty()) {
Node cur = queue.poll();
int hd = cur.hd;
TreeNode treeNode = cur.treeNode;
if (!map.containsKey(hd)) {
map.put(hd, new ArrayList<>());
}
map.get(hd).add(treeNode.val);
if (treeNode.left != null) {
queue.offer(new Node(treeNode.left, hd - 1));
minHd = Math.min(minHd, hd - 1);
}
if (treeNode.right != null) {
queue.offer(new Node(treeNode.right, hd + 1));
maxHd = Math.max(maxHd, hd + 1);
}
}
for (int i = minHd; i <= maxHd; i++) {
List<Integer> cur = map.get(i);
res.add(cur);
}
return res;
}
}