1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 * this.val = (val===undefined ? 0 : val)
5
 * this.left = (left===undefined ? null : left)
6
 * this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number[][]}
12
 */
13
var verticalTraversal = function (root) {
14
  let ans = [];
15
  let l = 0,
16
    ri = 0,
17
    mi = 0;
18
  const preOrder = (r = root, mid = 0, d = 0) => {
19
    if (!r) return;
20

21
    if (mid == 0) {
22
      if (ans.length < mi + 1) ans.push([]);
23
      ans[mi].push({ v: r.val, d });
24
    } else if (mid < 0) {
25
      if (mid < l) {
26
        l = mid;
27
        mi++;
28
        ans.unshift([{ v: r.val, d }]);
29
      } else {
30
        let idx = mi + mid;
31
        ans[idx].push({ v: r.val, d });
32
      }
33
    } else {
34
      if (mid > ri) {
35
        ri = mid;
36
        ans.push([{ v: r.val, d }]);
37
      } else {
38
        let idx = mi + mid;
39
        ans[idx].push({ v: r.val, d });
40
      }
41
    }
42

43
    preOrder(r.left, mid - 1, d + 1);
44
    preOrder(r.right, mid + 1, d + 1);
45
  };
46
  preOrder();
47
  const sortByDepthOrVal = (a, b) => {
48
    if (a.d == b.d) return a.v - b.v;
49
    return a.d - b.d;
50
  };
51
  ans = ans.map((col) => col.sort(sortByDepthOrVal).map((a) => a.v));
52
  return ans;
53
};