Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.
Find 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: for example, "ab" is lexicographically smaller than "aba". A leaf of a node is a node that has no children.)
Example 1:
Input: [0,1,2,3,4,3,4] Output: "dba"
Example 2:
Input: [25,1,3,1,3,0,2] Output: "adz"
Example 3:
Input: [2,2,1,null,1,0,null,0] Output: "abc"
Note:
- The number of nodes in the given tree will be between
1and1000. - Each node in the tree will have a value between
0and25.
给定一颗根结点为 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和1000之间。 - 树中的每个结点都有一个介于
0和25之间的值。
Runtime: 24 ms Memory Usage: 3.8 MB
1 /**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * public var val: Int
5 * public var left: TreeNode?
6 * public var right: TreeNode?
7 * public init(_ val: Int) {
8 * self.val = val
9 * self.left = nil
10 * self.right = nil
11 * }
12 * }
13 */
14 class Solution {
15 var ret:String = "~"
16 func smallestFromLeaf(_ root: TreeNode?) -> String {
17 dfs(root,"")
18 return ret
19 }
20
21 func dfs(_ cur: TreeNode?,_ s: String)
22 {
23 var s = s
24 if cur == nil {return}
25 s = String((97 + cur!.val).ASCII) + s
26 if cur?.left == nil && cur?.right == nil
27 {
28 if s < ret {ret = s}
29 }
30 dfs(cur?.left, s)
31 dfs(cur?.right, s)
32 }
33 }
34
35 //Int扩展方法
36 extension Int
37 {
38 //属性：ASCII值(定义大写为字符值)
39 var ASCII:Character
40 {
41 get {return Character(UnicodeScalar(self)!)}
42 }
43 }