Skip to content

Commit 5d61f01

Browse files
fishercoder1534fishercoder1534
committed
refactor 314
1 parent cc1b75c commit 5d61f01

File tree

1 file changed

+84
-73
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+84
-73
lines changed

‎src/main/java/com/fishercoder/solutions/_314.java

Lines changed: 84 additions & 73 deletions
Original file line numberDiff line numberDiff line change
@@ -9,8 +9,10 @@
99
import java.util.Queue;
1010
import java.util.TreeMap;
1111

12-
13-
/**Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).
12+
/**
13+
* 314. Binary Tree Vertical Order Traversal
14+
*
15+
* Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).
1416
1517
If two nodes are in the same row and column, the order should be from left to right.
1618
@@ -31,6 +33,7 @@
3133
[20],
3234
[7]
3335
]
36+
3437
Given binary tree [3,9,8,4,0,1,7],
3538
3
3639
/\
@@ -47,6 +50,7 @@
4750
[8],
4851
[7]
4952
]
53+
5054
Given binary tree [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),
5155
3
5256
/\
@@ -65,86 +69,93 @@
6569
[3,0,1],
6670
[8,2],
6771
[7]
68-
]*/
72+
]
73+
*/
6974
public class _314 {
70-
public List<List<Integer>> verticalOrder_using_treemap(TreeNode root) {
71-
List<List<Integer>> result = new ArrayList();
72-
if (root == null) {
73-
return result;
74-
}
75-
Queue<TreeNode> bfsQ = new LinkedList();
76-
Queue<Integer> indexQ = new LinkedList();
77-
TreeMap<Integer, List<Integer>> map = new TreeMap();
78-
bfsQ.offer(root);
79-
indexQ.offer(0);//we set the root as index 0, left will be negative, right will be positive
80-
while (!bfsQ.isEmpty()) {
81-
int qSize = bfsQ.size();
82-
for (int i = 0; i < qSize; i++) {
83-
TreeNode curr = bfsQ.poll();
84-
int index = indexQ.poll();
85-
if (map.containsKey(index)) {
86-
map.get(index).add(curr.val);
87-
} else if (!map.containsKey(index)) {
88-
List<Integer> list = new ArrayList();
89-
list.add(curr.val);
90-
map.put(index, list);
91-
}
92-
if (curr.left != null) {
93-
bfsQ.offer(curr.left);
94-
indexQ.offer(index - 1);
95-
}
96-
if (curr.right != null) {
97-
bfsQ.offer(curr.right);
98-
indexQ.offer(index + 1);
75+
public static class Solution1 {
76+
public List<List<Integer>> verticalOrder(TreeNode root) {
77+
List<List<Integer>> result = new ArrayList();
78+
if (root == null) {
79+
return result;
80+
}
81+
Queue<TreeNode> bfsQ = new LinkedList();
82+
Queue<Integer> indexQ = new LinkedList();
83+
TreeMap<Integer, List<Integer>> map = new TreeMap();
84+
bfsQ.offer(root);
85+
indexQ.offer(
86+
0);//we set the root as index 0, left will be negative, right will be positive
87+
while (!bfsQ.isEmpty()) {
88+
int qSize = bfsQ.size();
89+
for (int i = 0; i < qSize; i++) {
90+
TreeNode curr = bfsQ.poll();
91+
int index = indexQ.poll();
92+
if (map.containsKey(index)) {
93+
map.get(index).add(curr.val);
94+
} else if (!map.containsKey(index)) {
95+
List<Integer> list = new ArrayList();
96+
list.add(curr.val);
97+
map.put(index, list);
98+
}
99+
if (curr.left != null) {
100+
bfsQ.offer(curr.left);
101+
indexQ.offer(index - 1);
102+
}
103+
if (curr.right != null) {
104+
bfsQ.offer(curr.right);
105+
indexQ.offer(index + 1);
106+
}
99107
}
100108
}
109+
for (int i : map.keySet()) {
110+
result.add(map.get(i));
111+
}
112+
return result;
101113
}
102-
for (int i : map.keySet()) {
103-
result.add(map.get(i));
104-
}
105-
return result;
106114
}
107115

108-
public List<List<Integer>> verticalOrder_using_hashmap(TreeNode root) {
109-
List<List<Integer>> result = new ArrayList();
110-
if (root == null) {
111-
return result;
112-
}
113-
Queue<TreeNode> bfsQ = new LinkedList();
114-
Queue<Integer> indexQ = new LinkedList();
115-
HashMap<Integer, List<Integer>> map = new HashMap();
116-
bfsQ.offer(root);
117-
indexQ.offer(0);//we set the root as index 0, left will be negative, right will be positive
118-
int min = 0;
119-
int max = 0;
120-
while (!bfsQ.isEmpty()) {
121-
int qSize = bfsQ.size();
122-
for (int i = 0; i < qSize; i++) {
123-
TreeNode curr = bfsQ.poll();
124-
int index = indexQ.poll();
125-
if (map.containsKey(index)) {
126-
map.get(index).add(curr.val);
127-
} else if (!map.containsKey(index)) {
128-
List<Integer> list = new ArrayList();
129-
list.add(curr.val);
130-
map.put(index, list);
131-
}
132-
if (curr.left != null) {
133-
bfsQ.offer(curr.left);
134-
indexQ.offer(index - 1);
135-
min = Math.min(min, index - 1);
136-
}
137-
if (curr.right != null) {
138-
bfsQ.offer(curr.right);
139-
indexQ.offer(index + 1);
140-
max = Math.max(max, index + 1);
116+
public static class Solution2 {
117+
public List<List<Integer>> verticalOrder(TreeNode root) {
118+
List<List<Integer>> result = new ArrayList();
119+
if (root == null) {
120+
return result;
121+
}
122+
Queue<TreeNode> bfsQ = new LinkedList();
123+
Queue<Integer> indexQ = new LinkedList();
124+
HashMap<Integer, List<Integer>> map = new HashMap();
125+
bfsQ.offer(root);
126+
indexQ.offer(
127+
0);//we set the root as index 0, left will be negative, right will be positive
128+
int min = 0;
129+
int max = 0;
130+
while (!bfsQ.isEmpty()) {
131+
int qSize = bfsQ.size();
132+
for (int i = 0; i < qSize; i++) {
133+
TreeNode curr = bfsQ.poll();
134+
int index = indexQ.poll();
135+
if (map.containsKey(index)) {
136+
map.get(index).add(curr.val);
137+
} else if (!map.containsKey(index)) {
138+
List<Integer> list = new ArrayList();
139+
list.add(curr.val);
140+
map.put(index, list);
141+
}
142+
if (curr.left != null) {
143+
bfsQ.offer(curr.left);
144+
indexQ.offer(index - 1);
145+
min = Math.min(min, index - 1);
146+
}
147+
if (curr.right != null) {
148+
bfsQ.offer(curr.right);
149+
indexQ.offer(index + 1);
150+
max = Math.max(max, index + 1);
151+
}
141152
}
142153
}
154+
for (int i = min; i <= max; i++) {
155+
result.add(map.get(i));
156+
}
157+
return result;
143158
}
144-
for (int i = min; i <= max; i++) {
145-
result.add(map.get(i));
146-
}
147-
return result;
148159
}
149160

150161
}

0 commit comments

Comments
 (0)