Skip to content

Commit 57392f2

Browse files
fishercoder1534fishercoder1534
committed
add 988
1 parent f12bcd0 commit 57392f2

File tree

3 files changed

+136
-0
lines changed

3 files changed

+136
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -126,6 +126,7 @@ _If you like this project, please leave me a star._ ★
126126
|994|[Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_994.java) | |Easy| BFS
127127
|993|[Cousins in Binary Tree](https://leetcode.com/problems/cousins-in-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_993.java) | |Easy| Tree, BFS
128128
|989|[Add to Array-Form of Integer](https://leetcode.com/problems/add-to-array-form-of-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_989.java) | |Easy| Array
129+
|988|[Smallest String Starting From Leaf](https://leetcode.com/problems/smallest-string-starting-from-leaf/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_988.java) | |Medium| Tree, DFS
129130
|987|[Vertical Order Traversal of a Binary Tree](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_987.java) | |Medium| Recursion
130131
|985|[Sum of Even Numbers After Queries](https://leetcode.com/problems/sum-of-even-numbers-after-queries/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_985.java) | |Easy| Array
131132
|979|[Distribute Coins in Binary Tree](https://leetcode.com/problems/distribute-coins-in-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_979.java) | |Medium| Recursion

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

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
5+
import java.util.ArrayList;
6+
import java.util.Collections;
7+
import java.util.HashMap;
8+
import java.util.List;
9+
import java.util.Map;
10+
11+
/**
12+
* 988. Smallest String Starting From Leaf
13+
*
14+
* Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z':
15+
* a value of 0 represents 'a', a value of 1 represents 'b', and so on.
16+
* Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.
17+
* (As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba".
18+
* A leaf of a node is a node that has no children.)
19+
*
20+
* Example 1:
21+
* Input: [0,1,2,3,4,3,4]
22+
* Output: "dba"
23+
*
24+
* Example 2:
25+
* Input: [25,1,3,1,3,0,2]
26+
* Output: "adz"
27+
*
28+
* Example 3:
29+
* Input: [2,2,1,null,1,0,null,0]
30+
* Output: "abc"
31+
*
32+
* Note:
33+
* The number of nodes in the given tree will be between 1 and 8500.
34+
* Each node in the tree will have a value between 0 and 25.
35+
* */
36+
public class _988 {
37+
public static class Solution1 {
38+
public String smallestFromLeaf(TreeNode root) {
39+
List<String> paths = new ArrayList<>();
40+
Map<Integer, Character> map = new HashMap<>();
41+
map.put(0, 'a');
42+
map.put(1, 'b');
43+
map.put(2, 'c');
44+
map.put(3, 'd');
45+
map.put(4, 'e');
46+
map.put(5, 'f');
47+
map.put(6, 'g');
48+
map.put(7, 'h');
49+
map.put(8, 'i');
50+
map.put(9, 'j');
51+
map.put(10, 'k');
52+
map.put(11, 'l');
53+
map.put(12, 'm');
54+
map.put(13, 'n');
55+
map.put(14, 'o');
56+
map.put(15, 'p');
57+
map.put(16, 'q');
58+
map.put(17, 'r');
59+
map.put(18, 's');
60+
map.put(19, 't');
61+
map.put(20, 'u');
62+
map.put(21, 'v');
63+
map.put(22, 'w');
64+
map.put(23, 'x');
65+
map.put(24, 'y');
66+
map.put(25, 'z');
67+
dfs(root, "", paths, map);
68+
return findSmallest(paths);
69+
}
70+
71+
private String findSmallest(List<String> paths) {
72+
List<String> reversed = new ArrayList<>();
73+
for (String path : paths) {
74+
StringBuilder sb = new StringBuilder();
75+
sb.append(path);
76+
reversed.add(sb.reverse().toString());
77+
}
78+
Collections.sort(reversed);
79+
return reversed.get(0);
80+
}
81+
82+
private void dfs(TreeNode root, String path, List<String> paths, Map<Integer, Character> map) {
83+
if (root == null) {
84+
return;
85+
}
86+
path += map.get(root.val);
87+
if (root.left == null && root.right == null) {
88+
paths.add(path);
89+
}
90+
dfs(root.left, path, paths, map);
91+
dfs(root.right, path, paths, map);
92+
path = path.substring(0, path.length() - 1);
93+
}
94+
}
95+
}

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import com.fishercoder.solutions._988;
6+
import org.junit.BeforeClass;
7+
import org.junit.Test;
8+
9+
import java.util.Arrays;
10+
11+
import static org.junit.Assert.assertEquals;
12+
13+
public class _988Test {
14+
private static _988.Solution1 solution1;
15+
private static TreeNode root;
16+
17+
@BeforeClass
18+
public static void setup() {
19+
solution1 = new _988.Solution1();
20+
}
21+
22+
@Test
23+
public void test1() {
24+
root = TreeUtils.constructBinaryTree(Arrays.asList(0, 1, 2, 3, 4, 3, 4));
25+
assertEquals("dba", solution1.smallestFromLeaf(root));
26+
}
27+
28+
@Test
29+
public void test2() {
30+
root = TreeUtils.constructBinaryTree(Arrays.asList(25, 1, 3, 1, 3, 0, 2));
31+
assertEquals("adz", solution1.smallestFromLeaf(root));
32+
}
33+
34+
@Test
35+
public void test3() {
36+
root = TreeUtils.constructBinaryTree(Arrays.asList(2, 2, 1, null, 1, 0, null, 0));
37+
assertEquals("abc", solution1.smallestFromLeaf(root));
38+
}
39+
40+
}

0 commit comments

Comments
 (0)