最右后端笔试：二叉树最大路径和与温度数据结构

《面试题目》

1. 二叉树节点的值可正可负，怎样求一条非空路径的最大节点值之和？
2. 怎样设计 TemperatureNode，提供初始化、push、pop 和查询最小值的方法，并处理题目要求的 k 个元素范围？

《参考解析》

二叉树最大路径和

对每个节点计算“从当前节点出发、向下一侧延伸”的最大贡献。左右子树的负贡献都按零处理，向父节点只返回当前值加左右贡献中较大的一项；但更新全局答案时，可以把左右两侧的正贡献一起加到当前节点上。

全局答案不能从零开始，否则全为负数的树会误得零。每个节点只访问一次，时间复杂度 O(n)，递归空间取决于树高。这套解法适用于路径可在任意节点开始、结束且至少包含一个节点的定义；路径是否必须经过根节点，要以试卷题意为准。

先确认 k 的含义

原帖把 TemperatureNode 理解为类似最小栈，但没有完整保留 k 的作用以及 pop 的删除方向。如果要求整个栈的最小值，可以让每个栈节点同时保存截至该层的最小值，入栈、出栈和查询都为 O(1)。如果要求最近 k 次记录中的最小值，则更接近滑动窗口，可以用单调队列保存候选值及下标。

两种结构的删除语义不同，不能因为题面有 getmin 就直接套最小栈。实现前应确认重复值、元素不足 k 个、空结构查询和初始化的约定。

其余题目的记录边界

原帖还提到非降序数组分成 k 组以及一道矩阵题，但分组目标函数是作者自己的不确定理解，矩阵题也没有留下具体条件，因此无法还原为完整题目。单选涉及 MySQL、Java 程序与 Shell 输出，原帖未记录选项。