988

988. Smallest String Starting From Leaf (Medium)

Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find 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.)

 

Example 1:

Input: [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

Input: [25,1,3,1,3,0,2]
Output: "adz"

Example 3:

Input: [2,2,1,null,1,0,null,0]
Output: "abc"

 

Note:

1. The number of nodes in the given tree will be between 1 and 8500.
2. Each node in the tree will have a value between 0 and 25.

Companies:
Bloomberg

Related Topics:
Tree, Depth-first Search

Similar Questions:

• Sum Root to Leaf Numbers (Medium)
• Binary Tree Paths (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/smallest-string-starting-from-leaf/
// Author: github.com/lzl124631x
// Time: O(N + (logN)^2)
// Space: O(logN)
class Solution {
    string ans, path;
    void dfs(TreeNode *root) {
        if (!root) return;
        path += 'a' + root->val;
        if (!root->left && !root->right) {
            reverse(begin(path), end(path));
            if (ans.empty() || path < ans) ans = path;
            reverse(begin(path), end(path));
        } else {
            dfs(root->left);
            dfs(root->right);
        }
        path.pop_back();
    }
public:
    string smallestFromLeaf(TreeNode* root) {
        dfs(root);
        return ans;
    }
};