Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right.

idea

• 刚看到题目又是Binary Tree的print, 以前做过了: pre/in/post/level/clockwise. 主要还是遍历的顺序而已.
• 但是这里vertical没看懂. 后来看了印度人blog, 理解了, 其实很简单, 通过horizontal distance(横向距离root的距离)来判断是否在同一个垂直线上.

思路1

• 我先是用的dfs, 即遍历左右, 而且用TreeMap来按照horizontal distance保存list, 便利完后, 直接遍历TreeMap扫到list of list里面返回.

• 我这里有2个疑问了: rec(root.left)的时候, 是保存root.val还是root.left.val到map里?

• 过了90%的test, 但是fail了, 因为dfs终究是深度优先, 即左子树遍历完之后, 进入右子树. 从而使得result并没有完全按顺序了. 例如下图的结果在dfs的做法会得到[4,6]:

       5               
      / \       
     /   \      
    /     \     
   /       \    
   1       6       
    \           
     \          
     3           
    / \         
    2 4     

[1, 2]
[5, 3]
[6, 4] // 而不应该是[4,6]

• 解决方法也很简单, 建立一个wrapper class, 保存node, 以及level. 然后在result里面按照level, 对每一个list sort.

思路2

• 既然要保证上层的排先, 那么就自然是BFS. 但也要保存horizontal distance. 例如bfs loop到3, 那么hd是0, 从而loop到2是加入到-1的list, 4是加入到1的list. 所以我直接加了一个和bfs queue同进退的hd queue, 从而与每一个node对应, 这样在loop的时候就知道现在的hd是什么了.
• 所以问题的关键在于保存loop(bfs)/recursion(dfs)的时候的parent的hd.

• 代码如下

  public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Map<Integer, List<Integer>> map = new TreeMap<>();
    List<Integer> hd0 = new ArrayList<>();
    hd0.add(root.val);
    map.put(0, hd0);
  
    Queue<TreeNode> q = new LinkedList<>();
    Queue<Integer> hdq = new LinkedList<>();
    q.offer(root);
    hdq.offer(0);
  
    //int hd = 0;
  
    while (!q.isEmpty()) {
      int sz = q.size();
      for (int i = 0; i < sz; ++i) {
        TreeNode node = q.poll();
        int hd = hdq.poll();
        if (node.left != null) {
          if (!map.containsKey(hd - 1)) {
            map.put(hd - 1, new ArrayList<>());
          }
          map.get(hd - 1).add(node.left.val);
          q.offer(node.left);
          hdq.offer(hd - 1);
        }
        if (node.right != null) {
          if (!map.containsKey(hd + 1)) {
            map.put(hd + 1, new ArrayList<>());
          }
          map.get(hd + 1).add(node.right.val);
          q.offer(node.right);
          hdq.offer(hd + 1);
        }
      }
    }
  
    for (int hdist : map.keySet()) {
      result.add(map.get(hdist));
    }
    return result;
  }
  

• 但是这个方法显然可以优化. 是discuss里面用double-linked-list的2倍时间!
  • 我这里用了3个辅助data structure, 空间消耗大, 而且还多了从map复制到result的时间.