17th_Smallest_String_Starting_From_Leaf.md

Smallest String Starting From Leaf

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

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.

Approach 1

Recursive dfs

    std::deque<char> ans = {'a' + 26};

    void dfs(TreeNode* node, std::deque<char>& curr)
    {
        if (!node)
        {
            return;
        }
        curr.emplace_front(node->val + 'a');
        if (!node->left && !node->right)
        {
            ans = std::min(ans, curr);
        }
        dfs(node->left, curr);
        dfs(node->right, curr);
        curr.pop_front();
    }

    string smallestFromLeaf(TreeNode* root) {
        std::deque<char> curr;
        dfs(root, curr);
        return std::string(ans.begin(), ans.end());
    }

Approach 2

Iterative dfs

    string smallestFromLeaf(TreeNode* root) {
        std::string ans = {26 + 'a'};
        std::stack<std::pair<TreeNode*, std::string>> st;
        st.emplace(root, "");
        std::string temp{};
        while (!st.empty())
        {
            auto [node, prevS] = st.top();
            st.pop();
            prevS += node->val + 'a';
            if (!node->left && !node->right)
            {
                temp = std::move(prevS);
                std::reverse(temp.begin(), temp.end());
                ans = std::min(ans, temp);
            }
            if (node->left)
            {
                st.emplace(node->left, prevS);
            }
            if (node->right)
            {
                st.emplace(node->right, prevS);
            }
        }
        return ans;
    }

Approach 3

    std::vector<std::string> strings;
    void dfs(TreeNode* node, std::string& curr)
    {
        if (!node)
        {
            return;
        }
        curr += node->val + 'a';
        if (!node->left && !node->right)
        {
            std::string rev = curr;
            std::reverse(rev.begin(), rev.end());
            strings.emplace_back(std::move(rev));
        }
        dfs(node->left, curr);
        dfs(node->right, curr);
        curr.pop_back();
    }

    string smallestFromLeaf(TreeNode* root) {
        strings.clear();
        std::string curr = "";
        dfs(root, curr);
        std::sort(strings.begin(), strings.end());
        return strings[0];
    }