988. Smallest String Starting From Leaf
1. Description
You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters ‘a’ to ‘z’.
Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.
As a reminder, any shorter prefix of a string is lexicographically smaller.
- For example, “ab” is lexicographically smaller than “aba”.
A leaf of a node is a node that has no children.
2. Example
Example 1:
Input: root = [0,1,2,3,4,3,4]
Output: “dba”
Example 2:
Input: root = [25,1,3,1,3,0,2]
Output: “adz”
Example 3:
Input: root = [2,2,1,null,1,0,null,0]
Output: “abc”
3. Constraints
- The number of nodes in the tree is in the range [1, 8500].
- 0 <= Node.val <= 25
4. Solutions
Depth-First Search
n is the number of nodes in root
Time complexity: O(n):
Space complexity: O(n)
class Solution {
public:
string smallestFromLeaf(TreeNode *root) {
string path;
traverse_(root, path);
reverse(small_path_.begin(), small_path_.end());
return small_path_;
}
private:
string small_path_;
bool is_less_(const string &str1, const string &str2) {
for (int i = str1.size() - 1, j = str2.size() - 1; i >= 0 && j >= 0; --i, --j) {
if(str1[i] != str2[j]) {
return str1[i] < str2[j];
}
}
return true;
}
void traverse_(TreeNode *root, string &path) {
if (root != nullptr) {
path.push_back('a' + root->val);
if (root->left == nullptr && root->right == nullptr) {
if (small_path_.empty() || is_less_(path, small_path_)) {
small_path_ = path;
}
}
traverse_(root->left, path);
traverse_(root->right, path);
path.pop_back();
}
}
};