[LeetCode] 988. Smallest String Starting From Leaf

[grandyang]

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.

这道题给了一棵二叉树，说是结点值上的数字对应一个字母，让返回从叶结点到根结点的路径可以组成的字符串中按字母顺序排列最小的那个。其实这道题的本质就是找二叉树的路径，跟之前那道 Binary Tree Paths 一样，从叶结点往回找路径不是很方便，这里还是找从根结点到叶结点的路径，在组成字符串的时候，每次把字符加到前头就可以了，得到的还是从叶结点到根结点的顺序。这里还是使用递归来做，结果 res 初始化为 ~，博主最喜欢用一个表情符号，这么做的原因是其 ASCII 码值是大于z的，所以可以当初始值。在递归函数中，首先判空，否则将当前字符加到 cur 的最前面，然后判断若当前结点是叶结点，则用 cur 来更新结果 res，接下来对左右子结点分别调用递归函数即可，参见代码如下：

解法一：

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);
    }
};

我们也可以稍微写的简洁一些，让递归函数有返回值，递归函数中还要带个参数，首先判空，若为空，则返回 ~。否则将当前字符加到结果 res 前面，然后判断左右结点是否相同，其实就是判断是否均为 null，也就是判断是否是叶结点，是的话就返回 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 同步地址:

#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 题目讲解汇总(持续更新中...)