BFS Solution - Java - Accepted 9ms


  • 0
    P

    The correct solution here is the BFS way. Else maintaining the ordering becomes a nightmare.

    
    public class Solution {
        public List<List<Integer>> verticalOrder(TreeNode root) {
            // Map which keys on horizontal distance from the root
            // Any traversal on right is +1 and any traversal on left is -1
    
            Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
            List<List<Integer>> retList = new ArrayList<List<Integer>>();
            
            if (root == null) return retList;
            
            int hd = 0, depth = 0;
            bfs(map, root);
            
            // Sort they keys in increasing order
            Integer[] keys = map.keySet().toArray(new Integer[map.keySet().size()]);
            Arrays.sort(keys);
            
            for (int key : keys) {
                retList.add(map.get(key));
            }
            return retList;
        }
        
        void bfs(Map<Integer, List<Integer>> map, TreeNode root) {
            Deque<TreeNode> nodeQue = new ArrayDeque<TreeNode>();
            Deque<Integer> hdQue = new ArrayDeque<Integer>();
            
            nodeQue.offer(root);
            hdQue.offer(0);
            
            while (!nodeQue.isEmpty()) {
                root = nodeQue.pollFirst();
                int hd = hdQue.pollFirst();
                
                if (!map.containsKey(hd)) {
                    map.put(hd, new ArrayList<Integer>());
                }
                map.get(hd).add(root.val);
                
                if (root.left!=null) {
                    nodeQue.offer(root.left); hdQue.offer(hd-1);
                }
                if (root.right != null) {
                    nodeQue.offer(root.right); hdQue.offer(hd+1);
                }
            }
        }
    }

Log in to reply
 

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