零题目：算法（leetcode，附思维导图+全解）300题（124）二叉树最大路径和一个主题描述二解概览（思维导图）三全解面试官：题目你看的差不多了，怎么样，有什么想法吗？狂人张三：对于二叉树的题目，我们可以优先使用【递归】。面试官：哦？为什么是这样？疯子张三：生物书上有一句话——“结构与函数适配”，那我觉得“算法”里面也有类似的东西，比如“数据结构与算法适配”——仔细观察，你会发现，当前根节点和它的左右节点的结构是“同构的”，那我们自然会想到用“递归”。面试官：疯狂的张三：面试官（严肃脸）：旁白：4分41秒后，张三齐声写下了下面的代码。1方案11)代码：//方案1《原地更新-逆遍法(self)》。//Tips：二叉树的题目应该优先考虑递归。//思路：//1）状态初始化：resVal=Number.NEGATIVE_INFINITY（因为需要最大值，先设置为最大的负值）//2）核心1：根据情况。//3）核心2：遍历新树，更新最大resVal。//4)返回结果resVal。varmaxPathSum=function(root){//根据情况更新树上每个节点的值。constupdateTree=(root=null)=>{//1.1)递归出口1if(!root){return;}//1.2)递归出口2let{left,right,val}=root;如果((!left)&&(!right)){返回;}//2)递归体//2.1)更新左子树的值。更新树（左）；//2.2)更新右子树的值。更新树（右）；//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。constgetMaxValByNewTree=(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（因为需要最大值，所以先设置为最大的负值）letresVal=Number.NEGATIVE_INFINITY;//2）核心1：根据情况更新树上每个节点的值。更新树（根）；//3）核心2：遍历新树，更新最大resVal。getMaxValByNewTree（根）；//4)返回结果resVal。返回resVal;};张三疯子：怎么样，还是pass吧？面试官：鄙视。疯狂的张三：自信满满。面试官：仔细看你的解法，有没有遍历过两次？那么他们在这两次穿越中做了什么？我们可以只进行1次遍历吗——即合并遍历？旁白：面对面试官一键三问的问题（“暗示一键三下？？”），张某直接“直冒三滴冷汗”。疯子张三（脸色微白，仔细看了代码。恍然大悟）：1.确实遍历了两次。2、分以下任务：1）updateTree：遍历树，从左右子树的值和0中选出当前节点值的最大值，加到当前根节点的值中.并更新结果值resVal（因为此时的resVal可能是当前根节点、当前左右子树组成的路径值之和）。2）getMaxValByNewTree：更新结果值resVal（因为此时的resVal可能是在当前根节点获取的）。3、updateTree和getMaxValByNewTree中产生的操作好像可以合并到一起。Side：过了一会儿（4分11秒后），张三根据方案一和新的思路，写出了如下代码。2Scheme21)代码：//Scheme2《官方，递归方法。（本质：思路和Scheme1一致，但是少了一次树遍历——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。varmaxPathSum=function(root){//核心：递归处理！constmaxGain=(root=null)=>{//1)递归退出if(!root){return0;}//2）递归体//2.1）递归计算左右子节点的最大贡献值//只有在最大贡献值大于0时，才会选择对应的子节点constleftGain=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)返回当前根节点的最大贡献值。返回root.val+Math.max(leftGain,rightGain);}//1）状态初始化：resVal=Number.NEGATIVE_INFINITY//（因为需要最大值，所以先设置为最大的负值）。让resVal=Number.NEGATIVE_INFINITY;//2)核心：遍历新树，更新最大resVal。最大增益（根）；//3)返回结果resVal。returnresVal;}疯子张三（写完上面的代码，急忙问面试官）：这是最优解，算不算面试通过？面试官：孩子是可以教的~张三疯子：又一个offer，我马上要当CEO了。晚上应该去吃沙县小吃吧？还是兰州拉面？哎，选择太多也是一种烦恼！FourResourcesSharing&More1HistoricalArticles-Overview文章名称SolutionReadingVolume1.TwoSum(TwoSum)共3种2.7k+2。TwoNumbers(AddTwoNumbers)共有4种2.7k+3。无重复字符的最长子串（LongestSubstringWithoutRepeatingCharacters）2.6k+4共有3种。求两个正序数组的中位数（MedianofTwoSortedArrays）3种2.8k+5。最长回文子串（LongestPalindromicSubstring）共有4种2.8k+6。ZigZagConversion（之字折线转换）共2种1.9k+7。ReverseInteger（反向整数）共有2种2.4k+8。字符串转换整型(atoi)(StringtoInteger(atoi))共3种4.2k+9。PalindromeNumber（回文数）共3种4.3k+11.ContainerWithMostWater（容器最多水）共5种4.0k+12.IntegertoRoman（整数转罗马）共3种3.2k+13。罗马数字（RomantoInteger）共3种3.8k+14。LongestCommonPrefix（最长公共前缀）共4种3.0k+15。三数之和（3Sum）有3种60.7k+16。三数之和（3SumClosest）有3种4.7k+17。电话号码的字母组合共3种3.1k+18。四数之和（4Sum）一共有4种11.5k+19。删除链表的倒数第N个节点(RemoveNthNodeFromEndofList)共4种1.2k+20。ValidParentheses有2种类型1.8k+21。MergeTwoSortedLists有3种类型1.2k+22。GenerateParentheses有4种1.1k+23。合并k个升序链表（MergekSortedLists）一共4种0.9k+24。SwapNodesinPairs（交换节点对）一共3种0.5k+25。K组反向链表（ReverseNodesink-Group）共5种1.3k+26。RemoveDuplicatesinanorderedarray（RemoveDuplicatesfromSortedArray）共4种1.3k+27。移除元素（RemoveElement）共4种0.4k+28。实现strStr()（ImplementstrStr()）5种0.8k+29。将两个整数相除4种0.6k+30。SubstringwithConcatenationofAllWords)共3种0.6k+31。NextPermutation（下一个排列）共2种0.8k+32。LongestValidParentheses（最长有效括号）一共2种1.4k+33。SearchinRotatedSortedArray(SearchinRotatedSortedArray)共3种1.0k+34。FindFirstandLastPositionofElementinthesortedarray（FindFirstandLastPositionofElementinSortedArray）共3种0.5k+35。搜索插入位置（SearchInsertPosition）共3种0.3k+36。有效数独(ValidSudoku)共1种0.6k+38。出现顺序（CountandSay）共5种1.1k+39。组合和（CombinationSum）共3种1.4k+40。CombinationSumII（组合和II）共2种1.6k+41.缺失第一个正数（FirstMissingPositive）有3种1.2k+53。最大子数组和（MaximumSuarray）有3种0.3k+88。合并两个排序数组（MergeSortedArray）有3种0.4k+102。二叉树层序遍历（BinaryTreeLevelOrderTraversal）共3种0.4k+146。LRU缓存（LRUCache）一共2种0.5k+160。两个链表的交集（IntersectionofTwoLinkedLists）一共2种0.1k+200。岛屿数量有4种类型。0.1k+206。反向链表有3种类型。1.0k+215。KthLargestElementinanarray（KthLargestElementinanArray）共有3种0.5k+236。二叉树的最近公共祖先（LowestCommonAncestorofaBinaryTree）一共有3种0.1k+2119。ANumberAfteraDoubleReversal（ANumberAfteraDoubleReversal）一共有2种0.3k+2120。执行所有后缀指令（ExecutionofAllSuffixInstructionsStayinginaGrid），共1种0.4k+2124。CheckwhetherallA'sappearbeforeB（CheckifAllA'sAppearsBeforeAllB's），共4种0.4k+2125。NumberofLaserBeamsinaBank（一排激光束数量）共3种0.3k+2126。毁灭小行星（DestroyingAsteroids）共2种1.6k+2129。大写标题)2种0.6k+2130。链表2类型的最大孪生和0.6k+2133。检查是否每一行和每一列都包含整数（CheckifEveryRowandColumnContainsAllNumbers)共1种0.6k+2博主简介代码农三少，一位致力于编写极简但完整的问题解决方案（算法）的博主，专注于一个问题的多种解决方案和结构化思维，欢迎一起刷LeetCode~
