关于leetcode:124二叉树中的最大路径和-算法leetcode附思维导图-全部解法300题

零 题目：算法（leetcode，附思维导图 + 全副解法）300 题之（124）二叉树中的最大门路和

一 题目形容

二 解法总览（思维导图）

三 全副解法

面试官：题目看得差不多了吧，怎么样、有无思路呀？

狂徒张三：对于二叉树的题目，咱们能够优先思考应用【递归】。

面试官：哦？这是为什么呢？

狂徒张三：生物上书上有讲 —— “构造与性能相适应”，那我认为“算法”里，也有相似的货色，如 “数据结构与算法相适应” —— 仔细观察，你会发现，以后根节点、其左右节点的构造是 “同构” 的，那那么咱们天然会联想到应用 “递归”。

面试官：

狂徒张三：

面试官（一脸庄重）：

旁白：过了 4 分 41 秒，张三便齐刷刷的写完了如下代码。

1 计划 1

1)代码：

// 计划 1“就地更新 - 再次遍历法（本人）”。// 技巧：二叉树的题目应优先思考应用递归。// 思路：// 1）状态初始化：resVal = Number.NEGATIVE_INFINITY（因 要求最大值，故 先置为 最大的负数值）// 2）外围 1：依据状况，更新 树上各节点的值。// 3）外围 2：遍历新树，更新最大值 resVal。// 4）返回后果 resVal。var maxPathSum = function(root) {
    // 依据状况，更新 树上各节点的值。const updateTree = (root = null) => {
        // 1.1）递归进口 1
        if (!root) {return;}

        // 1.2）递归进口 2
        let {left, right, val} = root;
        if ((!left) && (!right)) {return;}

        // 2）递归主体
        // 2.1）更新 左子树的值。updateTree(left);
        // 2.2）更新 右子树的值。updateTree(right);
        
        // 2.3）更新 根节点的值。// 分 3 种状况：带上左子树的值 或 带上右子树的值 或 左、右子树值均不带。root.val = val + Math.max((left?.val || 0), (right?.val || 0), 0);

        // 2.4）更新后果值 resVal。resVal = Math.max(resVal, val + (left?.val || 0) + (right?.val || 0));
    };

    // 遍历新树，更新最大值 resVal。const getMaxValByNewTree = (root = null) => {
        // 1）递归进口
        if (!root) {return;}

        // 2）递归主体
        const {left, right, val} = root;
        // 2.1）根节点
        resVal = Math.max(resVal, val);
        // 2.2）左子树
        getMaxValByNewTree(left);
        // 2.3）右子树
        getMaxValByNewTree(right);
    };

    // 1）状态初始化：resVal = Number.NEGATIVE_INFINITY（因 要求最大值，故 先置为 最大的负数值）let resVal = Number.NEGATIVE_INFINITY;

    // 2）外围 1：依据状况，更新 树上各节点的值。updateTree(root);

    // 3）外围 2：遍历新树，更新最大值 resVal。getMaxValByNewTree(root);

    // 4）返回后果 resVal。return resVal;
};

狂徒张三：怎么样，还算过关吧？

面试官：一脸不屑。

狂徒张三：满脸自信。

面试官：你认真看下你这个解法，是不是遍历了 2 次？那么他们这 2 次遍历别离做了什么？咱们是否能够只进行 1 次遍历 —— 即进行遍历的合并？

旁白：面对面试官的一键 3 问（“暗示一键三连？？”），张间接“吓出了 3 滴冷汗”。

狂徒张三（面色略略发白，并仔仔细细的看了一遍代码。豁然开朗道）：

1、的确遍历了 2 次。2、分了做了如下工作：1）updateTree：遍历树，以后节点值从左、右子树的值和 0 中选出最大值，并加到以后根节点的值上。并 更新后果值 resVal（因为此时的 resVal 有可能是 有以后根节点、以后左、右子树一起组成的门路值之和）。2）getMaxValByNewTree：更新后果值 resVal（因为此时的 resVal 有可能是在以后根节点获得的）。3、看起来，updateTree、getMaxValByNewTree 中产生的操作能够合并到一起。

旁边：不一会（过了 4 分 11 秒），张三便基于计划 1 和新思路写完了如下的代码。

2 计划 2

1)代码：

// 计划 2“官网，递归法。（实质：跟计划 1 的思路是统一的，只是少了 1 次树的遍历 —— getMaxValByNewTree）”。// 参考：// 1）https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/

// 思路：// 1）状态初始化：resVal = Number.NEGATIVE_INFINITY 
//（因 要求最大值，故 先置为 最大的负数值）。// 2）外围：遍历新树，更新最大值 resVal。// 3）返回后果 resVal。var maxPathSum = function(root) {
    // 外围：递归解决！const maxGain = (root = null) => {
        // 1）递归进口
        if (!root) {return 0;}

        // 2）递归主体
        // 2.1）递归计算左右子节点的最大奉献值
        // 只有在最大奉献值大于 0 时，才会选取对应子节点
        const leftGain = Math.max(maxGain(root.left), 0),
            rightGain = Math.max(maxGain(root.right), 0),
            // 节点的最大门路和取决于该节点的值与该节点的左右子节点的最大奉献值
            priceNewpath = root.val + leftGain + rightGain;
        
        // 2.2）更新后果值 resVal。resVal = Math.max(resVal, priceNewpath);

        // 2.3）返回以后根节点的最大奉献值。return root.val + Math.max(leftGain, rightGain);
    }

    // 1）状态初始化：resVal = Number.NEGATIVE_INFINITY 
    //（因 要求最大值，故 先置为 最大的负数值）。let resVal = Number.NEGATIVE_INFINITY;
    
    // 2）外围：遍历新树，更新最大值 resVal。maxGain(root);

    // 3）返回后果 resVal。return resVal;
}

狂徒张三（写完了如上代码，急忙问面试官）：这算是最优解，算是通过面试了吧？

面试官：孺子可教也~

狂徒张三：

又 1 个 offer，而后马上就要出任 CEO 了，我早晨应该是去吃 沙县小吃 呢？还是 兰州拉面 呢？哎，抉择太多也是一种懊恼！

四 资源分享 & 更多

1 历史文章 – 总览

2 博主简介

码农三少，一个致力于编写 极简、但齐全题解（算法 ）的博主。
专一于 一题多解、结构化思维，欢送一起刷穿 LeetCode ~