从哈工大数据结构期末算法题出发：手把手教你用Python实现“删K位得最小数”和“二叉树最长路径”

从算法题到实战：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 边界情况与测试用例

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

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

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 二叉树路径算法对比

4. 实际应用场景扩展

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

删K位数字的应用场景：

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

二叉树最长路径的应用：

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

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