[LeetCode][Medium] 988. Smallest String Starting From Leaf

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

題目說明:

給定一個 Binary Tree，從這個 Binary Tree 中找出從 Leaf 到 Root 最小的單字

(最小的單字意味者字典排序， a -> z，短到長)

解題說明:

這題很直觀，就是直接從 Binary Tree 的 Root 訪問到 Leaf，

最後到 Leaf 之後再去依照字典排序比較要保留哪個單字，

途中保存 Node 的方式可以使用 vector ，亦或者是使用 string，

由於只需要訪問所有的 Node，所以這題的時間複雜度是 O (n)，

而因為我們始終只保留最短的單字，所以空間複雜度是 O (n)。

程式碼

class Solution {
public:
    string answer;
    string smallestFromLeaf(TreeNode* root) {
        answer = "";
        vector<int> nodes;
        if (root) traverseTree(root, nodes);
        return answer;
    }
    
    void updateAnswer(vector<int>& nodes) {
        bool flag = true;
        int length = answer.length();
        for (int i = nodes.size() - 1, j = 0; i >= 0 && j < length && flag; i--, j++) {
            if (nodes[i] < (answer[j] - 'a')) break;
            if (nodes[i] > (answer[j] - 'a')) flag = false;
        }
        if (flag) {
            answer = "";
            for (int i = nodes.size() - 1; i >= 0; i--) {
                answer = answer + char(nodes[i] + 'a');
            }
        }
    }
    
    void traverseTree(TreeNode* node, vector<int>& nodes) {
        if (node == NULL) return;
        nodes.push_back(node->val);
        if (node->left == NULL && node->right == NULL) {
            updateAnswer(nodes);
        }
        if (node->left) traverseTree(node->left, nodes);
        if (node->right) traverseTree(node->right, nodes);
        nodes.pop_back();
    }
};




結果

Runtime: 12 ms, faster than 81.38% of C++ online submissions for Smallest String Starting From Leaf.

Memory Usage: 19.9 MB, less than 74.16% of C++ online submissions for Smallest String Starting From Leaf.