# 988. Smallest String Starting From Leaf

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]
``````

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`.

``````class Solution {
public:
string smallestFromLeaf(TreeNode* root) {
string res = "~";
helper(root, "", res);
return res;
}
void helper(TreeNode* node, string cur, string& res) {
if (!node) return;
cur = string(1, node->val + 'a') + cur;
if (!node->left && !node->right) {
res = min(res, cur);
}
helper(node->left, cur, res);
helper(node->right, cur, res);
}
};
``````

``````class Solution {
public:
string smallestFromLeaf(TreeNode* root) {
return helper(root, "");
}
string helper(TreeNode* node, string res) {
if (!node) return "~";
res = string(1, node->val + 'a') + res;
return node->left == node->right ? res : min(helper(node->left, res), helper(node->right, res));
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/988

Sum Root to Leaf Numbers

Binary Tree Paths

https://leetcode.com/problems/smallest-string-starting-from-leaf/

https://leetcode.com/problems/smallest-string-starting-from-leaf/discuss/231102/C%2B%2B-3-lines

https://leetcode.com/problems/smallest-string-starting-from-leaf/discuss/231251/Java-2-Concise-DFS-codes-with-comment.

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation