2023年蔚来校招笔试题，比较难

将 脚本之家 设为“星标⭐”第一时间收到文章更新本文经数据结构和算法（id:sjjghsf）授权转载

下面这道题是力扣的第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;
}

  推荐阅读：