|
7 | 7 | importjava.util.PriorityQueue; |
8 | 8 | importjava.util.TreeMap; |
9 | 9 |
|
10 | | -/** |
11 | | - * 987. Vertical Order Traversal of a Binary Tree |
12 | | - * |
13 | | - * Given a binary tree, return the vertical order traversal of its nodes values. |
14 | | - * 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). |
15 | | - * 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). |
16 | | - * If two nodes have the same position, then the value of the node that is reported first is the value that is smaller. |
17 | | - * Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes. |
18 | | - * |
19 | | - * Example 1: |
20 | | - * |
21 | | - * 3 |
22 | | - * / \ |
23 | | - * 9 20 |
24 | | - * / \ |
25 | | - * 15 7 |
26 | | - * |
27 | | - * Input: [3,9,20,null,null,15,7] |
28 | | - * Output: [[9],[3,15],[20],[7]] |
29 | | - * Explanation: |
30 | | - * Without loss of generality, we can assume the root node is at position (0, 0): |
31 | | - * Then, the node with value 9 occurs at position (-1, -1); |
32 | | - * The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2); |
33 | | - * The node with value 20 occurs at position (1, -1); |
34 | | - * The node with value 7 occurs at position (2, -2). |
35 | | - * |
36 | | - * |
37 | | - * Example 2: |
38 | | - * |
39 | | - * 1 |
40 | | - * / \ |
41 | | - * 2 3 |
42 | | - * / \ / \ |
43 | | - * 4 5 6 7 |
44 | | - * |
45 | | - * Input: [1,2,3,4,5,6,7] |
46 | | - * Output: [[4],[2],[1,5,6],[3],[7]] |
47 | | - * Explanation: |
48 | | - * The node with value 5 and the node with value 6 have the same position according to the given scheme. |
49 | | - * However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6. |
50 | | - * |
51 | | - * Note: |
52 | | - * |
53 | | - * The tree will have between 1 and 1000 nodes. |
54 | | - * Each node's value will be between 0 and 1000. |
55 | | - * */ |
56 | 10 | publicclass_987 { |
57 | 11 | publicstaticclassSolution1 { |
58 | | -/**credit: https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/discuss/231148/Java-TreeMap-Solution*/ |
| 12 | +/** |
| 13 | + * credit: https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/discuss/231148/Java-TreeMap-Solution |
| 14 | + */ |
59 | 15 | publicList<List<Integer>>verticalTraversal(TreeNoderoot) { |
60 | 16 | TreeMap<Integer,TreeMap<Integer,PriorityQueue<Integer>>>map =newTreeMap<>(); |
61 | 17 | dfs(root,0,0,map); |
|