文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一顆根結點為 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 和 8500 之間。 樹中的每個結點都有一個介于 0 和 25 之間的值。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/smallest-string-starting-from-leaf
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

class Solution {string ans, temp; public:string smallestFromLeaf(TreeNode* root) {string path;dfs(root, path);return ans;}void dfs(TreeNode* root, string& path) {if(!root) return;path += root->val+'a';if(!root->left && !root->right){ //葉節點temp = path;reverse(temp.begin(), temp.end());if(ans == "")ans = temp;else if(ans > temp)ans = temp;}dfs(root->left, path);dfs(root->right, path);path.pop_back();//回溯} };

20 ms 19.2 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 988. 从叶结点开始的最小字符串（DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。