关于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 ~