Input:
[3,9,8,4,0,1,7,null,null,null,2,5]
(0's right child is 2 and 1's left child is 5)
3
/\
/ \
9 8
/\ /\
/ \/ \
4 01 7
/\
/ \
5 2
Output:
[
[4],
[9,5],
[3,0,1],
[8,2],
[7]
]
FB: Complexity!
Thoughts
Use map <col, list<val>> to record the col and list value pair. Use BFS to expand the tree to add entry
Code T O(V), S O(V)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
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, max = 0;
q.add(root); cols.add(0);
while(!q.isEmpty()){
TreeNode cur = q.poll();
int j = cols.poll();
// add <col, val> pair
if(!map.containsKey(j)) map.put(j, new ArrayList<Integer>());
map.get(j).add(cur.val);
// update the range of col value
min = Math.min(min, j);
max = Math.max(max, j);
// expand children
if(cur.left != null){
q.add(cur.left);
cols.add(j - 1);
}
if(cur.right != null){
q.add(cur.right);
cols.add(j+ 1);
}
}
// add all the list entry
for (int i = min ; i <= max; i++ ){
res.add(map.get(i));
}
return res;
}
}
Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
cols = collections.defaultdict(list)
queue = [(root,0)]
for node, col in queue:
if node:
cols[col].append(node.val)
queue += (node.left, col - 1), (node.right, col + 1)
return [cols[col] for col in sorted(cols)]