大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位同学拒了字节的校招offer，hr极力挽留，表示可以再给他提提base，但是楼主心意已决，虽然十分感动还是拒绝了hr的挽留。楼主一直在大厂实习，大厂的工作强度和工作时长让他非常排斥，所以拒绝了大厂的offer，想去追求生活平衡的工作。
评论区有同学表示果然大佬都是追着给offer，菜鸡面五轮甚至七八轮都拿不到offer。还有同学表示大佬的世界已经看不懂了，大佬对hr爱答不理，我却对hr高攀不起。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，我们今天分享一道字节面试算法原题「二叉树中的最大路径和」。
题目描述
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
举个例子：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
思路解析
首先定义变量 lmax表示root的左子树中能与root节点组成合法路径的节点组合的最大和。对于下图中的root节点，绿色的节点[1,3]就是其左子树中能与root组成合法路径的节点组合，此时lmax = 4。同样定义 rmax表示root右子树中能与root节点组成合法路径的节点组合的最大和。定义 res保存二叉树中合法路径最大和。
本题可以使用递归，难点在于不能简单的把二叉树的最大路径和分解为左子树的最大路径和与右子树的最大路径和的组合。我们通过递归来获取左子树中能与root组成合法路径的节点组合最大和lmax与右子树中能与root组成合法路径的节点组合最大和rmax，并在递归函数中更新res。
下面讨论三种更新res的最基本情况。
所有节点的值均为正数。
此时合法路径最大和res = lmax + rmax + root->val。
孩子节点中存在值为负数。
此时为负数值的节点不能包含到路径中，否则路径的和会变小。所以这个时候需要对上面的公式进行改造一下res = max(lmax, 0) + max(rmax, 0) + root->val。
根节点值为负数。
这时根节点可能会导致新的路径和比左子树的最大路径和或右子树的最大路径和小，所以需要进一步对上面的公式进行改造res = max(res, max(lmax, 0) + max(rmax, 0) + root->val)。
通过上面的讨论我们得到了最大路径和的推导公式。那么lmax和rmax怎么更新呢？
如下图，root'的lmax = max(lmax, rmax) + root->val。
同样地可以去计算rmax的值。
根据上面的讨论我们需要在递归函数中更新res、lmax、rmax，详细代码如下。
c++代码
class Solution {
public:
int maxPathSum(TreeNode* root) {
int res = root->val;
dfs(root, res);
return res;
}
int dfs(TreeNode* root, int& res) {
if (!root) {
return 0;
}
int lmax = dfs(root->left, res);
lmax = max(lmax, 0);
int rmax = dfs(root->right, res);
rmax = max(rmax, 0);
res = max(res, root->val + lmax + rmax);
return root->val + max(lmax, rmax);
}
};
python代码
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res = float('-inf')
self.dfs(root)
return self.res
def dfs(self, root):
if not root:
return 0
lmax = max(self.dfs(root.left), 0)
rmax = max(self.dfs(root.right), 0)
self.res = max(self.res, root.val + lmax + rmax)
return root.val + max(lmax, rmax)
复杂度分析
时间复杂度： 因为需要遍历所有的节点，所以时间复杂度和二叉树节点的总数相关。
空间复杂度： 因为用到了递归，需要用到栈来保存递归函数，栈的最大长度为二叉树的高度，所以空间复杂度和二叉树的高度相关。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
