[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) { a...