Smallest String Starting From Leaf: หาสตริงเล็กที่สุดจากใบไปราก

โจทย์

กำหนด Binary Tree โหนดมีค่า 0-25 แทน 'a'-'z' หา Lexicographically Smallest String จาก ใบ (leaf) ไป ราก (root)

ตัวอย่าง: Tree [25,1,3,1,3,0,2] → Path 0→3→25 = "adz" (เล็กที่สุด)

       25 (z)
      /  \
     1    3
    / \  / \
   1  3 0  2
      / \
     0   2
Leaves: 1, 0, 2, 0, 2
Paths:  1→1→25="b b z" (bbz)
        0→3→1→25="a d b z" (ad bz)
        2→3→1→25="c d b z" (cdbz)
        0→3→25="a d z" (adz) ← smallest!
        2→3→25="c d z" (cdz)

อัลกอริทึม: DFS + Path Tracking

• DFS จาก root เก็บ path (list of chars)
• ถึง leaf: สร้าง string จาก leaf→root (reverse path) เปรียบเทียบกับ global min
• Backtrack: pop path

การติดตั้ง (Python Implementation)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def smallestFromLeaf(self, root: TreeNode) -> str:
        self.best = "~"  # Character after 'z' in ASCII
        
        def dfs(node, path):
            if not node:
                return
            
            # Add current character
            path.append(chr(node.val + ord('a')))
            
            # Leaf node
            if not node.left and not node.right:
                # Path is root→leaf, need leaf→root (reverse)
                candidate = ''.join(reversed(path))
                if candidate < self.best:
                    self.best = candidate
            
            # Recurse
            dfs(node.left, path)
            dfs(node.right, path)
            
            # Backtrack
            path.pop()
        
        dfs(root, [])
        return self.best

# Helper
def build_tree(vals):
    if not vals:
        return None
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    for i, node in enumerate(nodes):
        if node:
            li, ri = 2*i+1, 2*i+2
            if li < len(nodes):
                node.left = nodes[li]
            if ri < len(nodes):
                node.right = nodes[ri]
    return nodes[0]

# ทดสอบ
ob = Solution()
root = build_tree([25,1,3,1,3,0,2])
print(ob.smallestFromLeaf(root))  # "adz"

# ทดสอบเพิ่ม
root2 = build_tree([0,1,2,3,4,3,4])  # Multiple paths
print(ob.smallestFromLeaf(root2))

Output

adz
...

Complexity

• Time: O(n × h) worst case (n nodes, h height, string compare O(h)) → O(n²) worst, O(n log n) average
• Space: O(h) - recursion stack + path

Optimization: String Building

แทน list + reverse ใช้ string concatenation แบบ prepend (แต่ Python string immutable → O(h²) ต่อ path) ใช้ list + join ตอนท้ายเร็วกว่า

สรุป

Smallest String From Leaf ใช้ DFS สำรวจทุก root-to-leaf path สร้าง string leaf→root เปรียบเทียบ lexicographically เก็บค่าน้อยที่สุด ใช้ "~" เป็นค่าเริ่มต้นเพราะมากกว่า 'z' ใน ASCII

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ