[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

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,4]Output: "dba" 

Example 2:

input: [25,2]Output: "adz" 

Example 3:

input: @H_404_80@[2,null,0]Output: "abc"

Note:

The number of nodes in the given tree will be between 1 and 1000. 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：

输入：[0,4]输出："dba"

示例 2：

输入：[25,2]输出："adz"

示例 3：

输入：[2,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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     var ret:String = "~"16     func smallestFromLeaf(_ root: TreeNode?) -> String {17         dfs(root,"")18         return ret19     }20         21     func dfs(_ cur: TreeNode?,_ s: String)22     {23         var s = s24         if cur == nil {return}25         s = String((97 + cur!.val).ASCII) + s26         if cur?.left == nil && cur?.right == nil27         {28             if s < ret {ret = s}29         }30         dfs(cur?.left,s)31         dfs(cur?.right,s)32     }33 }34     35 //Int扩展方法  36 extension Int37 {38     //属性：ASCII值(定义大写为字符值)39     var ASCII:Character 40     {41         get {return Character(UnicodeScalar(self)!)}42     }43 }

总结

以上是内存溢出为你收集整理的[Swift Weekly Contest 122]LeetCode988. 从叶结点开始的最小字符串 | Smallest String Starting From Leaf全部内容，希望文章能够帮你解决[Swift Weekly Contest 122]LeetCode988. 从叶结点开始的最小字符串 | Smallest String Starting From Leaf所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。