8000 refactor 662 · albertuz/Leetcode@79c5614 · GitHub
[go: up one dir, main page]
Skip to content

Commit 79c5614

Browse files
fishercoder1534fishercoder1534
committed
refactor 662
1 parent 4cb151c commit 79c5614

File tree

2 files changed

+37
-36
lines changed

2 files changed

+37
-36
lines changed

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

Lines changed: 30 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,6 @@
99
import java.util.Map;
1010
import java.util.Queue;
1111

12-
1312
/**
1413
* 662. Maximum Width of Binary Tree
1514
*
@@ -72,38 +71,40 @@
7271
Note: Answer will in the range of 32-bit signed integer.
7372
*/
7473
public class _662 {
75-
/**
76-
* Use a map to store the node to value map,
77-
* we use root as index 1, then its left child is 2*i-1 and right child is 2*i
78-
*/
79-
public int widthOfBinaryTree(TreeNode root) {
80-
if (root == null) {
81-
return 0;
82-
}
74+
public static class Solution1 {
75+
/**
76+
* Use a map to store the node to value map,
77+
* we use root as index 1, then its left child is 2*i-1 and right child is 2*i
78+
*/
79+
public int widthOfBinaryTree(TreeNode root) {
80+
if (root == null) {
81+
return 0;
82+
}
8383

84-
Queue<Map.Entry<TreeNode, Integer>> queue = new LinkedList<>();
85-
queue.offer(new AbstractMap.SimpleEntry<>(root, 1));
86-
int max = 1;
87-
while (!queue.isEmpty()) {
88-
int size = queue.size();
89-
List<Map.Entry<TreeNode, Integer>> list = new ArrayList<>();
90-
for (int i = 0; i < size; i++) {
91-
Map.Entry<TreeNode, Integer> curr = queue.poll();
92-
if (curr.getKey().left != null) {
93-
Map.Entry<TreeNode, Integer> newEntry = new AbstractMap.SimpleEntry<>(curr.getKey().left, curr.getValue() * 2 - 1);
94-
queue.offer(newEntry);
95-
list.add(newEntry);
84+
Queue<Map.Entry<TreeNode, Integer>> queue = new LinkedList<>();
85+
queue.offer(new AbstractMap.SimpleEntry<>(root, 1));
86+
int max = 1;
87+
while (!queue.isEmpty()) {
88+
int size = queue.size();
89+
List<Map.Entry<TreeNode, Integer>> list = new ArrayList<>();
90+
for (int i = 0; i < size; i++) {
91+
Map.Entry<TreeNode, Integer> curr = queue.poll();
92+
if (curr.getKey().left != null) {
93+
Map.Entry<TreeNode, Integer> newEntry = new AbstractMap.SimpleEntry<>(curr.getKey().left, curr.getValue() * 2 - 1);
94+
queue.offer(newEntry);
95+
list.add(newEntry);
96+
}
97+
if (curr.getKey().right != null) {
98+
Map.Entry<TreeNode, Integer> newEntry = new AbstractMap.SimpleEntry<>(curr.getKey().right, curr.getValue() * 2);
99+
queue.offer(newEntry);
100+
list.add(newEntry);
101+
}
96102
}
97-
if (curr.getKey().right != null) {
98-
Map.Entry<TreeNode, Integer> newEntry = new AbstractMap.SimpleEntry<>(curr.getKey().right, curr.getValue() * 2);
99-
queue.offer(newEntry);
100-
list.add(newEntry);
103+
if (list.size() > 1) {
104+
max = Math.max(list.get(list.size() - 1).getValue() - list.get(0).getValue() + 1, max);
101105
}
102106
}
103-
if (list.size() > 1) {
104-
max = Math.max(list.get(list.size() - 1).getValue() - list.get(0).getValue() + 1, max);
105-
}
107+
return max;
106108
}
107-
return max;
108109
}
109110
}

‎src/test/java/com/fishercoder/_662Test.java

Lines 8000 changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -12,34 +12,34 @@
1212
import static junit.framework.TestCase.assertEquals;
1313

1414
public class _662Test {
15-
private static _662 test;
15+
private static _662.Solution1 solution1;
1616
private static TreeNode root;
1717
private static int expected;
1818

1919
@BeforeClass
2020
public static void setup() {
21-
test = new _662();
21+
solution1 = new _662.Solution1();
2222
}
2323

2424
@Test
2525
public void test1() {
2626
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 3, 2, 5, 3, null, 9));
2727
expected = 4;
28-
assertEquals(expected, test.widthOfBinaryTree(root));
28+
assertEquals(expected, solution1.widthOfBinaryTree(root));
2929
}
3030

3131
@Test
3232
public void test2() {
3333
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 3, null, 5, 3));
3434
expected = 2;
35-
assertEquals(expected, test.widthOfBinaryTree(root));
35+
assertEquals(expected, solution1.widthOfBinaryTree(root));
3636
}
3737

3838
@Test
3939
public void test3() {
4040
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 3, 2, 5));
4141
expected = 2;
42-
assertEquals(expected, test.widthOfBinaryTree(root));
42+
assertEquals(expected, solution1.widthOfBinaryTree(root));
4343
}
4444

4545
@Test
@@ -48,13 +48,13 @@ public void test3() {
4848
public void test4() {
4949
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 3, 2, 5, null, null, 9, 6, null, null, null, null, null, null, 7));
5050
expected = 8;
51-
assertEquals(expected, test.widthOfBinaryTree(root));
51+
assertEquals(expected, solution1.widthOfBinaryTree(root));
5252
}
5353

5454
@Test
5555
public void test5() {
5656
root = TreeUtils.constructBinaryTree(Arrays.asList(1));
5757
expected = 1;
58-
assertEquals(expected, test.widthOfBinaryTree(root));
58+
assertEquals(expected, solution1.widthOfBinaryTree(root));
5959
}
6060
}

0 commit comments

Comments
 (0)
0