Smallest String Starting From Leaf: Chuỗi Nhỏ Nhất Lexicographically Từ Lá Đến Gốc

Đề bài: Cây nhị phân, node value 0-25 mapping 'a'-'z'. Tìm chuỗi lexicographically nhỏ nhất từ leaf lên root.

Ví dụ: Tree [25,1,3,1,3,0,2] → path 0→3→25 = "adz" (leaf 0, parent 3, root 25).

Ý tưởng: DFS Tìm Tất Cả Path Leaf→Root, Lấy Min

DFS pre-order, maintain path hiện tại. Khi gặp leaf, xây string từ leaf lên root (reverse path), so sánh với global min.

Code Python

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 = '~'  # Char after 'z' in ASCII
        
        def dfs(node, path):
            if not node:
                return
            
            # Add current char to path (root->leaf direction)
            path.append(chr(node.val + ord('a')))
            
            if not node.left and not node.right:
                # Leaf: build string leaf->root (reverse path)
                candidate = ''.join(reversed(path))
                if candidate < self.best:
                    self.best = candidate
            else:
                dfs(node.left, path)
                dfs(node.right, path)
            
            path.pop()  # Backtrack
        
        dfs(root, [])
        return self.best

# Helper build tree
def build_tree(vals):
    if not vals: return None
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    kids = nodes[::-1]
    root = kids.pop()
    for node in nodes:
        if node:
            if kids: node.left = kids.pop()
            if kids: node.right = kids.pop()
    return root

# Test
root = build_tree([25,1,3,1,3,0,2])
ob = Solution()
print(ob.smallestFromLeaf(root))  # "adz"

Tối ưu: Không Cần Lưu Cả Path, So Sánh Trực Tiếp

Truyền string built so far (leaf→current), so sánh khi về root. Nhưng Python string immutable → O(h²) nếu concat. List + join tốt hơn.

Phân tích

• Time: O(n * h) worst case (n leaf, each path length h, string compare O(h)).
• Space: O(h) recursion + path.
• Có thể tối ưu so sánh lexicographic on-the-fly để cắt sớm.

Kết luận

DFS thu thập path, tại leaf build string reverse, update global min. Đơn giản, đúng. Pattern: tree path to string, lexicographic min.