Easy understand JAVA solution with BFS + TreeMap


  • 0
    S
    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);
            queue.add(root);
            
            while (!queue.isEmpty()) {
                TreeNode node = queue.remove();
                int column = mapNodeColumnNum.get(node);
                if (!mapColumnRes.containsKey(column)) mapColumnRes.put(column, new ArrayList<Integer>());
                mapColumnRes.get(column).add(node.val);
                
                if(node.left != null) {
                    queue.add(node.left);
                    mapNodeColumnNum.put(node.left, column-1);
                }
                if(node.right != null) {
                    queue.add(node.right);
                    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.