最近看到一份HR的简历，真的是让我大吃一惊，简直逆天！真的是刷新了我对HR的认知。
你看这简历里写的：在职期间，通过与部门及员工本人面谈，成功劝退员工4人，未支付赔偿金；处理员工矛盾、工伤调查两起（居然没提报工伤）……你没看错，HR居然“省了赔偿金”，这可不是一般的HR操作！🤯
这种操作真的是太“精明”了。HR显然是用“成本最小化”的方式来考虑问题，而对于公司来说，这样的HR就像是一个不需要“Debug”的程序，直接解决了“错误”。
总的来说，这样的简历从老板的角度来看，确实是得到了某种“极致优化”，但是从员工和公司长期发展来看，可能就不那么“完美”了。
算法题：在每个树行中找最大值
今天我想和大家聊聊一个算法题，虽然它看起来很简单，但在实际编程过程中却充满了各种巧妙的思路。题目是：在每个树行中找最大值，我知道这个问题一提出来，可能有些人会觉得很基础，甚至可能觉得有点儿小儿科。但事实上，这道题对我来说挺有意思的，特别是思考如何用不同的方法来解决它。
首先，让我们来仔细看一下这个问题的核心：给定一颗二叉树，我们需要找出每一层中的最大值。听起来像是层次遍历的经典问题，但如果你不小心，可能就会陷入一些无谓的复杂化中。
经典解法：层次遍历 + 最大值
我们可以用层次遍历（BFS，广度优先搜索）来解决这个问题。大家应该都知道，层次遍历通常使用队列（queue）来实现。我们每次取出队列中的节点，然后将它们的左右孩子节点加入队列，直到遍历完所有节点。我们在遍历的过程中，记录下每一层的最大值。
代码实现
首先，先给大家展示一个简单的实现方式：
from collections import deque
# 定义二叉树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 层次遍历 + 找每层最大值
def largestValues(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level_max = float('-inf') # 初始化当前层最大值为负无穷
for _ in range(level_size):
node = queue.popleft()
level_max = max(level_max, node.val) # 更新最大值
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_max) # 当前层的最大值添加到结果中
return result
在这段代码中，我们通过一个deque队列来帮助进行层次遍历。每一层的最大值会通过level_max变量来维护。每当我们遍历完当前层的节点，就将该层的最大值添加到结果列表result中。
细节分析
这道题的关键在于层次遍历，这是一个非常常见的技术。在实际编程中，很多算法题都会要求我们通过队列来处理这种逐层的问题，因为队列是先进先出的数据结构，正好符合层次遍历的特点。我们在遍历每一层时，只有当前层的节点被处理完了，下一层的节点才会被加入队列，从而保证了逐层处理。
我们还需要注意几个点：
空树的情况：在实际问题中，我们要先判断根节点是否为空。如果为空，就直接返回一个空列表，避免错误。 更新最大值：在每一层，我们需要记录当前层的最大值。在这个过程中，我们用了 max函数来不断更新最大值。虽然Python中有很多方法能找到最大值，但在这里用max函数效率非常高，而且简洁明了。队列操作：队列的操作是核心， queue.popleft()将当前节点从队列中取出，queue.append()则是将当前节点的子节点加入队列。这些操作是保证层次遍历正确进行的关键。
优化空间
虽然这道题本身并不复杂，但有些地方可以优化或者给出一些拓展的思路。比如说，如果树特别深，而每一层的节点数比较少，队列可能会占用很多空间。对于这种情况，我们可以考虑使用DFS（深度优先搜索）来代替BFS进行遍历，虽然DFS的实现更麻烦一些，但可以减少内存消耗。
如果你用DFS实现的话，大致会是这样的思路：
def dfs(node, level, result):
if not node:
return
# 如果当前层还没有记录最大值，初始化
if level == len(result):
result.append(node.val)
else:
result[level] = max(result[level], node.val)
# 递归遍历左右子树
dfs(node.left, level + 1, result)
dfs(node.right, level + 1, result)
def largestValuesDFS(root):
result = []
dfs(root, 0, result)
return result
结语
看完这个题目，你是不是觉得层次遍历真的很重要？不仅仅是这道题，很多与树相关的题目都离不开这个技巧。如果你还没有掌握层次遍历，强烈建议好好练一练，后面遇到树的题目会轻松不少。
不过，虽然这道题看起来很简单，但是它涉及到了很多我们在解决实际问题时需要面对的情况——如何优化内存、如何高效地更新结果。算法看似简单，背后却充满了思考的空间。
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。
