【二叉树】从叶结点开始的最小字符串

0x00 题目

给定一颗根结点为 root 的二叉树
树中的每一个结点都有一个 [0, 25] 范围内的值
分别代表字母 a 到 z

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

注：
字符串中任何较短的前缀在 字典序上 都是 较小 的
例如，在字典序上 “ab” 比 “aba” 要小
叶结点是指没有子结点的结点

---

0x01 思路

因为字符串的构成是
从叶子节点向根节点的方向
所以要使用后序遍历方式

---

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法：

func smallestFromLeaf(_ root: TreeNode?) -> String {
    var res = ""
    var s = ""
    
    func dfs(_ root: TreeNode?) {
        guard let r = root else { return }
        
        // 数字转字符，a - 97
        let c = Character(UnicodeScalar(97 + r.val)!)
        
        // 字符转字符串，拼接
        s += String(c)
        
        // 到了叶子节点
        if r.left == nil && r.right == nil {
            var t = String(s)
            
            // 倒序
            t = String(t.reversed())
            
            // 比较大小
            if res.isEmpty || t < res {
                res = t
            }
        }
        
        dfs(r.left)
        dfs(r.right)
        
        // 返回上一层，删除最后一个，也就是回溯算法
        s.removeLast()
    }
    
    dfs(root)
    return res
}

---

0x03 我的作品

欢迎体验我的作品之一：小五笔小程序
五笔学习好帮手~
微信搜索 XWubi 即可~

---