987. Vertical Order Traversal of a Binary Tree.md

987. Vertical Order Traversal of a Binary Tree

---

Difficulty : Medium

Related Topics : Tree、HashTable

---

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Note:

• The tree will have between 1 and 1000 nodes.
• Each node's value will be between 0 and 1000.

---

Solution

• mine
  • Java
    • BFS Runtime: 3 ms, faster than 84.53%, Memory Usage: 39.5 MB, less than 66.33% of Java online submissions

      // O(N * logN)time
      // O(N)space
      int max = 0, min = 0;
      
      public List<List<Integer>> verticalTraversal(TreeNode root) {
          List<List<Integer>> res = new ArrayList<>();
      
          HashMap<Integer, List<Pair>> map = new HashMap<>();
          LinkedList<Pair> list = new LinkedList<>();
          if (root != null) list.add(new Pair(0, 0, root));
      
          while (!list.isEmpty()) {
              Pair pair = list.removeFirst();
              int x = pair.x;
              int y = pair.y;
              max = Math.max(max, x);
              min = Math.min(min, x);
              TreeNode node = pair.node;
              List<Pair> value = map.getOrDefault(x, new LinkedList<>());
              value.add(pair);
              map.put(x, value);
              if (node.left != null) list.add(new Pair(x - 1, y + 1, node.left));
              if (node.right != null) list.add(new Pair(x + 1, y + 1, node.right));
          }
          for (int i = min; i <= max; i++) {
              List<Pair> t = map.get(i);
              if (t != null) {
                  Collections.sort(t);
                  List<Integer> sub = new LinkedList<>();
                  for (Pair p : t) {
                      sub.add(p.node.val);
                  }
                  res.add(sub);
              }
          }
          return res;
      }
      
      class Pair implements Comparable<Pair> {
          public int x;
          public int y;
          public TreeNode node;
      
          public Pair(int x, int y, TreeNode node) {
              this.x = x;
              this.y = y;
              this.node = node;
          }
      
          @Override
          public int compareTo(Pair other) {
              if (this.x != other.x) return Integer.compare(this.x, other.x);
              else if (this.y != other.y) return Integer.compare(this.y, other.y);
              else return Integer.compare(this.node.val, other.node.val);
          }
      }
      

---

• the most votes

• BFS Runtime: 2 ms, faster than 99.74%, Memory Usage: 39.9 MB, less than 5.61% of Java online submissions

  // O(N * logN)time
  // O(N)space
  int min=0, max=0;
  Map<Integer, List<Integer>> map = new HashMap();
  public List<List<Integer>> verticalTraversal(TreeNode root) {
      List<List<Integer>> res = new ArrayList();
      if(root==null) return res;
      Queue<TreeNode> qt = new LinkedList();
      Queue<Integer> qi = new LinkedList();
      qt.add(root);
      qi.add(0);//not root.val
      while(!qt.isEmpty()){
          int size = qt.size();
          Map<Integer,List<Integer>> tmp = new HashMap();
          for(int i=0;i<size;i++){
              TreeNode cur = qt.poll();
              int idx = qi.poll();
              if(!tmp.containsKey(idx)) tmp.put(idx, new ArrayList<Integer>());
              tmp.get(idx).add(cur.val);
              if(idx<min)  min = idx;
              if(idx>max)  max = idx;
              if(cur.left!=null){
                  qt.add(cur.left);
                  qi.add(idx-1);
              }
              if(cur.right!=null){
                  qt.add(cur.right);
                  qi.add(idx+1);
              }
          }
          for(int key : tmp.keySet()){
              if(!map.containsKey(key)) map.put(key, new ArrayList<Integer>());
              List<Integer> list = tmp.get(key);
              Collections.sort(list);
              map.get(key).addAll(list);
          }
  
      }
      for (int i=min; i<=max; i++){
          List<Integer> list = map.get(i);
          res.add(list);
      }
      return res;
  }
  

• DFS Runtime: 2 ms, faster than 99.74%, Memory Usage: 39.8 MB, less than 19.39% of Java online submissions

  // O(N * logN)time
  // O(N)space
  List<Location> locations;
  public List<List<Integer>> verticalTraversal(TreeNode root) {
      // Each location is a node's x position, y position, and value
      locations = new ArrayList();
      dfs(root, 0, 0);
      Collections.sort(locations);
  
      List<List<Integer>> ans = new ArrayList();
      ans.add(new ArrayList<Integer>());
  
      int prev = locations.get(0).x;
  
      for (Location loc: locations) {
          // If the x value changed, it's part of a new report.
          if (loc.x != prev) {
              prev = loc.x;
              ans.add(new ArrayList<Integer>());
          }
  
          // We always add the node's value to the latest report.
          ans.get(ans.size() - 1).add(loc.val);
      }
  
      return ans;
  }
  
  public void dfs(TreeNode node, int x, int y) {
      if (node != null) {
          locations.add(new Location(x, y, node.val));
          dfs(node.left, x-1, y+1);
          dfs(node.right, x+1, y+1);
      }
  }
  
  class Location implements Comparable<Location>{
      int x, y, val;
      Location(int x, int y, int val) {
          this.x = x;
          this.y = y;
          this.val = val;
      }
  
      @Override
      public int compareTo(Location that) {
          if (this.x != that.x)
              return Integer.compare(this.x, that.x);
          else if (this.y != that.y)
              return Integer.compare(this.y, that.y);
          else
              return Integer.compare(this.val, that.val);
      }
  }
  

---