Problem description:

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.

Examples 1:

Input: [3,9,20,null,null,15,7]

1
2
3
4
5
6
7
  3
 /\
/  \
9  20
   /\
  /  \
 15   7

Output:

1
2
3
4
5
6
[
  [9],
  [3,15],
  [20],
  [7]
]

Examples 2:

Input: [3,9,8,4,0,1,7]

1
2
3
4
5
6
7
    3
   /\
  /  \
  9   8
 /\  /\
/  \/  \
4  01   7

Output:

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

Examples 3:

Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0’s right child is 2 and 1’s left child is 5)

1
2
3
4
5
6
7
8
9
10
    3
   /\
  /  \
  9   8
 /\  /\
/  \/  \
4  01   7
   /\
  /  \
  5   2

Output:

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

Solution:

The idea is to construct a map with the vertical index and every value of that level. By using map, we can get ascending index by default.

Then we use BFS to walk though the tree. If it’s a left node, then the index should be smaller. If it’s a right node, the index should be greater

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        mapping = defaultdict(list)
        queue = deque([(root, 0)])
        
        while queue:
            l = len(queue)
            for i in range(l):
                frontNode, col = queue.popleft()
                if frontNode.left: queue.append((frontNode.left, col-1))
                if frontNode.right: queue.append((frontNode.right, col+1))
                mapping[col].append(frontNode.val)
        
        return [mapping[i] for i in sorted(mapping)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        //BFS
        map<int, vector<int>> map;
        vector<vector<int>> res;
        if(!root)
            return res;
        
        queue<pair<int, TreeNode*>> q;
        q.push({0, root});
        
        while(!q.empty()){
            auto tmp= q.front(); q.pop();
            map[tmp.first].push_back(tmp.second->val);
            if(tmp.second->left) q.push({tmp.first-1, tmp.second->left});
            if(tmp.second->right) q.push({tmp.first+1, tmp.second->right});
        }
        
        for(auto m: map)
            res.push_back(m.second);
        return res;
    }
    
};

time complexity:
map use $O(log n)$ for insertion, total is n node, so $O(nlogn)$

DFS

Similar idea but we need row information to know which row comes first. Because during inorder traverse, on the right subtree, we would traverse bottom left first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        mapping = defaultdict(list)
        
        def dfs(root, row, col):
            if not root:
                return
            dfs(root.left, row+1, col-1)
            mapping[col].append((root.val, row))
            dfs(root.right, row+1, col+1)
        
        dfs(root, 0, 0)
        res = []
        for k, v in sorted(mapping.items()): # sort by col
            res.append([x[0] for x in sorted(v, key=lambda x:x[1])]) # sort by row
        return res

reference:
http://www.cnblogs.com/grandyang/p/5278930.html
https://goo.gl/yfKXEE