2023年蔚来校招笔试题，比较难
The following article is from 数据结构和算法 Author 博哥
下面这道题是力扣的第124题，有一定的难度，不仅在蔚来的面试中遇到，在其他很多他大厂也有同学遇到过，可见这是一道非常受欢迎的试题，最好能够完全掌握，以后面试再遇到这题的时候就能应对自如了，我们来看下都有哪些大厂考过。
--------------华为---------------
--------------字节---------------
--------------快手---------------
--------------字节---------------
--------------字节---------------
--------------虾皮---------------
--------------蔚来---------------
问题描述
来源：LeetCode第124题
难度：困难
路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次 。该路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其最大路径和。
问题分析
这题有个重要条件就是同一个节点在一条路径中至多出现 1 次，我们先画个图来消化下哪些路径是有效的，哪些是无效的。
通过上面的图我们发现，如果一个路径是有效的，那么选择了他的父节点之后，他的两个子节点最多只能选择一个，如上面的图（1）中，如果我们选择了 2 的父节点，那么他的两个子节点我们最多只能选择一个。如果没有选择父节点，那么他的两个子节点都是可以选择的。我们可以从下往上，计算选择当前节点并且最多只能选择一个子节点的最大值。因为如果最多只能选择一个子节点，我们还可以选择他的父节点，往上继续计算。如果两个子节点都选择了，就不能在选择父节点了，没法在往上计算了。因为这里是求最大值，如果两个子树的最大路径都是负数，我们可以都不选，如下面图中所示：
所以大致代码我们可以先写出来：
private int dfs(TreeNode root) {
if (root == null)
return 0;
int left = dfs(root.left);// 左子树的最大路径（包含左子节点）
int right = dfs(root.right);// 左子树的最大路径（包含左子节点）
// 返回包含当前节点的路径，路径不能分叉，所以两个子节点我们最多
// 只能选择一个，如果两个子树的最大路径都小于 0 ，我们就不选了。
return Math.max(0, Math.max(left, right)) + root.val;
}
这个和求最大子序和很类似，只不过一个是计算数组的一个是计算二叉树的。上面代码计算的是最多只能选择一个子节点，但实际上最大路径和我们是可以选择两个子节点的，所以这里我们从下往上计算的时候，如果两个子树的最大值都是正数，我们就都选择，然后计算下他们的值，最后保存最大的即可，来看下代码：
int max = Integer.MIN_VALUE;// 记录最大的路径和
public int maxPathSum(TreeNode root) {
dfs(root);
return max;
}
// 包含当前节点 root 的最大路径
private int dfs(TreeNode root) {
if (root == null)
return 0;
int left = dfs(root.left);// 左子树的最大路径（包含左子节点）
int right = dfs(root.right);// 左子树的最大路径（包含左子节点）
// 两个子树计算的值只要是正的，我们都选择。
int curMax = Math.max(0, left) + Math.max(0, right) + root.val;
// 记录最大值
max = Math.max(max, curMax);
// 返回包含当前节点的路径
return Math.max(0, Math.max(left, right)) + root.val;
}