从算法题到实战：Python实现“删K位最小数”与“二叉树最长路径”全解析

当数据结构从试卷走向代码编辑器，抽象的理论突然变得具体而生动。本文将带你用Python实现两道经典算法题："删K位得最小数"和"二叉树最长路径"，不仅还原解题思路，更注重工程实践中的各种细节处理。

1. 删K位数字问题：贪心算法的精妙应用

"给定一个数字字符串，删除其中K个字符后使剩余数字最小"——这道看似简单的题目背后隐藏着贪心算法的典型应用场景。想象一下信用卡号输入错误需要删除几位数字的场景，或者文件版本号需要精简时的处理逻辑。

1.1 问题分析与核心思路

贪心算法的关键在于局部最优导致全局最优。对于数字"1432219"要删除3位，我们不应该随机删除，而是从左到右寻找应该删除的数字：

1. 维护一个结果栈
2. 遍历每个数字时，只要当前数字比栈顶小且还能删除(k>0)，就弹出栈顶
3. 将当前数字压入栈
4. 如果遍历完k仍大于0，从末尾继续删除

def removeKdigits(num: str, k: int) -> str:
    stack = []
    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # 处理剩余需要删除的情况
    final_stack = stack[:-k] if k > 0 else stack
    # 去除前导零并处理空字符串情况
    return ''.join(final_stack).lstrip('0') or '0'

1.2 边界情况与测试用例

实际编码时需要特别注意以下边界条件：

测试用例	预期结果	说明
"10200", 1	"200"	删除1后需去除前导零
"10", 2	"0"	全部删除应返回0
"12345", 2	"123"	单调递增时删除末尾
"10001", 4	"0"	多个零的特殊处理

提示：在实际面试中，能正确处理各种边界情况往往比算法本身更重要

2. 二叉树最长路径：递归与迭代的双解

二叉树的最大深度问题看似简单，但当需要获取具体路径而非仅长度时，复杂度就显著提升。这在文件系统路径查找、组织架构层级分析等场景都有实际应用。

2.1 递归解法：深度优先的直观实现

递归是解决树问题的自然思路，后序遍历可以优雅地获取深度信息：

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

def longestPath(root: TreeNode) -> List[int]:
    max_path = []
    
    def dfs(node):
        nonlocal max_path
        if not node:
            return []
        left_path = dfs(node.left)
        right_path = dfs(node.right)
        # 选择更长的子路径
        longer_path = left_path if len(left_path) > len(right_path) else right_path
        current_path = longer_path + [node.val]
        # 更新全局最长路径
        if len(current_path) > len(max_path):
            max_path = current_path
        return current_path
    
    dfs(root)
    return max_path

2.2 迭代解法：显式栈管理状态

对于大型树或担心递归栈溢出的情况，迭代解法更可靠：

def longestPathIterative(root: TreeNode) -> List[int]:
    if not root:
        return []
    
    stack = [(root, [root.val])]
    max_path = []
    
    while stack:
        node, path = stack.pop()
        if len(path) > len(max_path):
            max_path = path
        if node.right:
            stack.append((node.right, path + [node.right.val]))
        if node.left:
            stack.append((node.left, path + [node.left.val]))
    
    return max_path

两种方法各有优劣：

• 递归：代码简洁，但深度过大可能栈溢出
• 迭代：性能稳定，适合大规模数据，但代码稍复杂

3. 算法优化与性能对比

理解算法的时间空间复杂度是工程实现的关键环节。

3.1 删K位算法复杂度分析

• 时间复杂度：O(n)，每个元素最多入栈出栈一次
• 空间复杂度：O(n)，最坏情况需要存储整个字符串

优化点：

• 提前终止：当剩余需要删除的数字数等于剩余未处理数字数时直接处理
• 并行处理：超长字符串可分块处理

3.2 二叉树路径算法对比

方法	时间复杂度	空间复杂度	适用场景
递归	O(n)	O(h)	树高度适中
迭代	O(n)	O(n)	树特别深或不确定深度

4. 实际应用场景扩展

这两个算法看似学术，实则有着广泛的实际应用：

删K位数字的应用场景：

• 数据压缩：去除冗余数字
• 金融交易：处理输错的金额
• 版本控制：精简过长的版本号

二叉树最长路径的应用：

• 文件系统：查找最深嵌套目录
• 网络路由：寻找最长匹配路径
• 组织结构：分析最长汇报链

在实现这些业务逻辑时，我们往往需要对基础算法进行适当改造。例如文件系统路径查找可能需要同时记录路径字符串而非仅长度，这时算法框架不变，只需调整存储的信息类型。