[LeetCode] 314. Binary Tree Vertical Order Traversal

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., 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.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Example 2:

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

Example 3:

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]

Example 4:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

二叉树的垂直遍历。

例子应该解释的很清楚了，思路是BFS层序遍历，需要用到一个index变量记录子节点相对于根节点的偏移量，同时需要用hashmap<偏移量，相同偏移量的节点组成的list>把相同偏移量的节点放在一起。

首先BFS层序遍历还是跟一般的BFS差不多，但是这里我做了两个queue，一个存放节点，一个存放每个节点的偏移量（注意这里实际只存了X坐标的偏移量，这个题是有followup的，987题），这样BFS遍历的时候，可以同时得到被遍历节点的偏移量。min和max的存在是记录最左和最右的偏移量，这样最后输出res的时候就可以从左往右按顺序输出了。

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public List<List<Integer>> verticalOrder(TreeNode root) {
18         List<List<Integer>> res = new ArrayList<>();
19         // corner case
20         if (root == null) {
21             return res;
22         }
23         // normal case
24         HashMap<Integer, List<Integer>> map = new HashMap<>();
25         Queue<TreeNode> queue = new LinkedList<>();
26         Queue<Integer> column = new LinkedList<>();
27         queue.offer(root);
28         column.offer(0);
29         int min = 0;
30         int max = 0;
31         while (!column.isEmpty()) {
32             TreeNode node = queue.poll();
33             int col = column.poll();
34             if (!map.containsKey(col)) {
35                 map.put(col, new ArrayList<Integer>());
36             }
37             map.get(col).add(node.val);
38             if (node.left != null) {
39                 queue.offer(node.left);
40                 column.add(col - 1);
41                 min = Math.min(min, col - 1);
42             }
43             if (node.right != null) {
44                 queue.offer(node.right);
45                 column.add(col + 1);
46                 max = Math.max(max, col + 1);
47             }
48         }
49 
50         for (int i = min; i <= max; i++) {
51             res.add(map.get(i));
52         }
53         return res;
54     }
55 }

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {number[][]}
 4  */
 5 var verticalOrder = function (root) {
 6     let res = [];
 7     // corner case
 8     if (root == null) {
 9         return res;
10     }
11 
12     // normal case
13     let map = new Map();
14     let queue = [];
15     queue.push([root, 0]);
16     let min = 0;
17     let max = 0;
18     while (queue.length > 0) {
19         let cur = queue.shift();
20         let node = cur[0];
21         let col = cur[1];
22         if (!map.has(col)) {
23             map.set(col, []);
24         }
25         map.get(col).push(node.val);
26         if (node.left) {
27             queue.push([node.left, col - 1]);
28             min = Math.min(min, col - 1);
29         }
30         if (node.right) {
31             queue.push([node.right, col + 1]);
32             max = Math.max(max, col + 1);
33         }
34     }
35 
36     for (let i = min; i <= max; i++) {
37         res.push(map.get(i));
38     }
39     return res;
40 };