# 987. Vertical Order Traversal of a Binary Tree

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.

## My notes.

Mind the case.

[0,8,1,null,null,3,2,null,4,5,null,null,7,6]

```
0
8 1
3 2
4,5
6 7
```

Rendered by Leetcode, with my lines added

￼

## My Solution

/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */ class Solution { /** * @param TreeNode $root * @return Integer[][] */ function verticalTraversal($root) { $result = []; $this->traversalHelper($root,0,0,$result); // Sort by col, from left to right ksort($result); foreach($result as &$rs){ $new_sub = []; // foreach col, sort by depth from top to bottom ksort($rs); foreach($rs as &$r){ // Same depth, sort by value asc, according to spec asort($r); $new_sub = array_merge($new_sub,$r); } $rs = $new_sub; } return $result; } // Recursion, go through the tree function traversalHelper($root, $pos,$depth, &$result) { if($root !== null){ if(!isset($result[$pos])){ $result[$pos] = []; } if(!isset($result[$pos][$depth])){ $result[$pos][$depth] = []; } $result[$pos][$depth][] = $root->val; $this->traversalHelper($root->left, $pos - 1,$depth+1, $result); $this->traversalHelper($root->right, $pos + 1,$depth+1, $result); } } }

## 0 Comments