Java,BFS+HashMap, concise and easy understanding


  • 0
    B
    public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(root == null) {
      return res;
    }
    HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    Queue<Integer> level = new LinkedList<Integer>();
    queue.add(root);
    level.add(0);
    while(!queue.isEmpty()) {
      TreeNode temp = queue.poll();
      int col = level.poll();
      if(!map.containsKey(col)) {
        map.put(col, new ArrayList<Integer>());
      }
      map.get(col).add(temp.val);
      if(temp.left != null) {
        queue.add(temp.left);
        level.add(col - 1);
      }
      if(temp.right != null) {
        queue.add(temp.right);
        level.add(col + 1);
      }
    }
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for(Integer item : map.keySet()) {
      min = Math.min(min, item);
      max = Math.max(max, item);
    }
    for(int i = min; i <= max; i++) {
      res.add(map.get(i));
    }
    return res;
    

    }


Log in to reply
 

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