Skip to content

Latest commit

 

History

History
112 lines (83 loc) · 3.54 KB

988-smallest-string-starting-from-leaf.md

File metadata and controls

112 lines (83 loc) · 3.54 KB

988. Smallest String Starting From Leaf - 从叶结点开始的最小字符串

给定一颗根结点为 root 的二叉树,书中的每个结点都有一个从 0 到 25 的值,分别代表字母 'a' 到 'z':值 0 代表 'a',值 1 代表 'b',依此类推。

找出按字典序最小的字符串,该字符串从这棵树的一个叶结点开始,到根结点结束。

(小贴士:字符串中任何较短的前缀在字典序上都是较小的:例如,在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。)

 

示例 1:

输入:[0,1,2,3,4,3,4]
输出:"dba"

示例 2:

输入:[25,1,3,1,3,0,2]
输出:"adz"

示例 3:

输入:[2,2,1,null,1,0,null,0]
输出:"abc"

 

提示:

  1. 给定树的结点数介于 1 和 8500 之间。
  2. 树中的每个结点都有一个介于 0 和 25 之间的值。

题目标签:Tree / Depth-first Search

题目链接:LeetCode / LeetCode中国

题解

Language Runtime Memory
cpp 28 ms 19.9 MB
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<char> tmp;
    string res;
    void dfs(TreeNode* node) {
        /* be care of:
         [0,null,1]
        */
        if (!node) {
            return;
        }
        char c = node->val + 'a';
        tmp.push_back(c);
        // leaf node
        if (!node->left && !node->right) {
            stringstream ss;
            for (int i = tmp.size() - 1; i >= 0; i--)
                ss << tmp[i];
            if (res.empty())
                res = ss.str();
            else
                res = min(res, ss.str());
        } else {
            if (node->left)
                dfs(node->left);
            if (node->right)
                dfs(node->right);
        }
        tmp.pop_back();
    }
    
    string smallestFromLeaf(TreeNode* root) {
        dfs(root);
        return res;
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();