[Swift Weekly Contest 122]LeetCode988. 从叶结点开始的最小字符串 | Smallest String Starting From Leaf

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:

[Swift Weekly Contest 122]LeetCode988. 从叶结点开始的最小字符串 | Smallest String Starting From Leaf

Input: [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

[Swift Weekly Contest 122]LeetCode988. 从叶结点开始的最小字符串 | Smallest String Starting From Leaf

Input: [25,1,3,1,3,0,2]
Output: "adz"

Example 3:

[Swift Weekly Contest 122]LeetCode988. 从叶结点开始的最小字符串 | Smallest String Starting From Leaf

Input: [2,2,1,null,1,0,null,0]
Output: "abc"

Note:

  1. The number of nodes in the given tree will be between 1 and 1000.
  2. Each node in the tree will have a value between 0 and 25.

给定一颗根结点为 root 的二叉树,书中的每个结点都有一个从 0 到 25 的值,分别代表字母 'a'到 'z':值 0 代表 'a',值 1 代表 'b',依此类推。

找出按字典序最小的字符串,该字符串从这棵树的一个叶结点开始,到根结点结束。

(小贴士:字符串中任何较短的前缀在字典序上都是较小的:例如,在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。)

 

示例 1:

[Swift Weekly Contest 122]LeetCode988. 从叶结点开始的最小字符串 | Smallest String Starting From Leaf

输入:[0,1,2,3,4,3,4]
输出:"dba"

示例 2:

[Swift Weekly Contest 122]LeetCode988. 从叶结点开始的最小字符串 | Smallest String Starting From Leaf

输入:[25,1,3,1,3,0,2]
输出:"adz"

示例 3:

[Swift Weekly Contest 122]LeetCode988. 从叶结点开始的最小字符串 | Smallest String Starting From Leaf

输入:[2,2,1,null,1,0,null,0]
输出:"abc"

 

提示:

  1. 给定树的结点数介于 1 和 1000 之间。
  2. 树中的每个结点都有一个介于 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 }

 

上一篇:设计模式-Composite(创建型模式) 用于 递归构建 树 状 的组合结构,与Decorator的区别是 Composite旨在通过构造子类而添加新操作,而Decorator直接添加新操作。


下一篇:多版本并发控制 MVCC简介