540. Smallest Leaf Word
Each node of the binary tree root holds a number from 1 to 26, standing for a letter: 1 is 'a', 2 is 'b', and so on up to 26 for 'z'. For every leaf (a node with no children), read the letters along the path that starts at that leaf and climbs up to the root, forming a word whose first letter is the leaf and whose last letter is the root. Return the lexicographically smallest of these words. Compare normally, and note that a word which is a proper prefix of another counts as smaller. If the tree is empty, return the empty string.
Example 1
- Input:
- root = [2,3,1,4,null,null,5]
- Output:
- "dcb"
- Explanation:
The leaf 4 gives "dcb" and the leaf 5 gives "eab", so "dcb" is the smallest.
Example 2
- Input:
- root = [1]
- Output:
- "a"
- Explanation:
The single node is both root and leaf, giving the word "a".
Example 3
- Input:
- root = [2,1,2,null,null,1]
- Output:
- "ab"
- Explanation:
The two leaves give "ab" and "abb"; the first is a prefix of the second and therefore smaller.
Constraints
0 ≤ number of nodes ≤ 500
1 ≤ Node.val ≤ 26
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n * h)
- Space
- O(n * h)