[binary tree] the minimum string starting from the leaf node

0x00 subject

Given a root node as root Two fork tree
Every node in the tree has a [0, 25] Values in range
Respectively representing letters a To z

return Smallest in lexicographic order String
The string from one of the trees leaf Start
To end of root

notes ：
Any shorter prefix in the string is in Dictionary Preface All are smaller Of
for example , In dictionary order “ab” Than “aba” smaller
Leaf node refers to node without child node

---

0x01 Ideas

Because the composition of the string is
from Leaf node towards The root node The direction of
So use In the following order Traverse the way

---

0x02 solution

Language ：Swift

Tree node ：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
    }
}

solution ：

func smallestFromLeaf(_ root: TreeNode?) -> String {
    var res = ""
    var s = ""
    
    func dfs(_ root: TreeNode?) {
        guard let r = root else { return }
        
        //  Number to character ,a - 97
        let c = Character(UnicodeScalar(97 + r.val)!)
        
        //  Character to string , Splicing 
        s += String(c)
        
        //  At the leaf node 
        if r.left == nil && r.right == nil {
            var t = String(s)
            
            //  In reverse order 
            t = String(t.reversed())
            
            //  Compare the size 
            if res.isEmpty || t < res {
                res = t
            }
        }
        
        dfs(r.left)
        dfs(r.right)
        
        //  Go back to the previous level , Delete the last one , Backtracking algorithm 
        s.removeLast()
    }
    
    dfs(root)
    return res
}

---

0x03 My work

Welcome to experience one of my works ： Small five pen small program
Wubi learning is a good helper ~
WeChat search XWubi that will do ~

---