Easy understand JAVA solution with BFS + TreeMap

  • 0
    public class Solution {
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if (root == null) return res;
            // <TreeNode, column number>
            HashMap<TreeNode, Integer> mapNodeColumnNum = new HashMap<TreeNode, Integer>();
            // <column number, all node's val which nodes have same column num>
            TreeMap<Integer, List<Integer>> mapColumnRes = new TreeMap<Integer, List<Integer>>();
            // queue for BFS
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            mapNodeColumnNum.put(root, 0);
            while (!queue.isEmpty()) {
                TreeNode node = queue.remove();
                int column = mapNodeColumnNum.get(node);
                if (!mapColumnRes.containsKey(column)) mapColumnRes.put(column, new ArrayList<Integer>());
                if(node.left != null) {
                    mapNodeColumnNum.put(node.left, column-1);
                if(node.right != null) {
                    mapNodeColumnNum.put(node.right, column+1);
            for(int i : mapColumnRes.keySet()) res.add(mapColumnRes.get(i));
            return res;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.