988. Smallest String Starting From Leaf

2023, Mar 21 2 mins read

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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();
        }
    }
};