零 题目:算法(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 历史文章 – 总览
文章名称 | 解法 | 浏览量 |
---|---|---|
1. 两数之和(Two Sum) | 共 3 种 | 2.7 k+ |
2. 两数相加(Add Two Numbers) | 共 4 种 | 2.7 k+ |
3. 无反复字符的最长子串(Longest Substring Without Repeating Characters) | 共 3 种 | 2.6 k+ |
4. 寻找两个正序数组的中位数(Median of Two Sorted Arrays) | 共 3 种 | 2.8 k+ |
5. 最长回文子串(Longest Palindromic Substring) | 共 4 种 | 2.8 k+ |
6. Z 字形变换(ZigZag Conversion) | 共 2 种 | 1.9 k+ |
7. 整数反转(Reverse Integer) | 共 2 种 | 2.4 k+ |
8. 字符串转换整数 (atoi)(String to Integer (atoi)) | 共 3 种 | 4.2 k+ |
9. 回文数(Palindrome Number) | 共 3 种 | 4.3 k+ |
11. 盛最多水的容器(Container With Most Water) | 共 5 种 | 4.0 k+ |
12. 整数转罗马数字(Integer to Roman) | 共 3 种 | 3.2 k+ |
13. 罗马数字转整数(Roman to Integer) | 共 3 种 | 3.8 k+ |
14. 最长公共前缀(Longest Common Prefix) | 共 4 种 | 3.0 k+ |
15. 三数之和(3Sum) | 共 3 种 | 60.7 k+ |
16. 最靠近的三数之和(3Sum Closest) | 共 3 种 | 4.7 k+ |
17. 电话号码的字母组合(Letter Combinations of a Phone Number) | 共 3 种 | 3.1 k+ |
18. 四数之和(4Sum) | 共 4 种 | 11.5 k+ |
19. 删除链表的倒数第 N 个结点(Remove Nth Node From End of List) | 共 4 种 | 1.2 k+ |
20. 无效的括号(Valid Parentheses) | 共 2 种 | 1.8 k+ |
21. 合并两个有序链表(Merge Two Sorted Lists) | 共 3 种 | 1.2 k+ |
22. 括号生成(Generate Parentheses) | 共 4 种 | 1.1 k+ |
23. 合并 K 个升序链表(Merge k Sorted Lists) | 共 4 种 | 0.9 k+ |
24. 两两替换链表中的节点(Swap Nodes in Pairs) | 共 3 种 | 0.5 k+ |
25. K 个一组翻转链表(Reverse Nodes in k-Group) | 共 5 种 | 1.3 k+ |
26. 删除有序数组中的反复项(Remove Duplicates from Sorted Array) | 共 4 种 | 1.3 k+ |
27. 移除元素(Remove Element) | 共 4 种 | 0.4 k+ |
28. 实现 strStr()(Implement strStr()) | 共 5 种 | 0.8 k+ |
29. 两数相除(Divide Two Integers) | 共 4 种 | 0.6 k+ |
30. 串联所有单词的子串(Substring with Concatenation of All Words) | 共 3 种 | 0.6 k+ |
31. 下一个排列(Next Permutation) | 共 2 种 | 0.8 k+ |
32. 最长无效括号(Longest Valid Parentheses) | 共 2 种 | 1.4 k+ |
33. 搜寻旋转排序数组(Search in Rotated Sorted Array) | 共 3 种 | 1.0k+ |
34. 在排序数组中查找元素的第一个和最初一个地位(Find First and Last Position of Element in Sorted Array) | 共 3 种 | 0.5 k+ |
35. 搜寻插入地位(Search Insert Position) | 共 3 种 | 0.3 k+ |
36. 无效的数独(Valid Sudoku) | 共 1 种 | 0.6 k+ |
38. 外观数列(Count and Say) | 共 5 种 | 1.1 k+ |
39. 组合总和(Combination Sum) | 共 3 种 | 1.4 k+ |
40. 组合总和 II(Combination Sum II) | 共 2 种 | 1.6 k+ |
41. 缺失的第一个负数(First Missing Positive) | 共 3 种 | 1.2 k+ |
53. 最大子数组和(Maximum Subarray) | 共 3 种 | 0.3k+ |
88. 合并两个有序数组(Merge Sorted Array) | 共 3 种 | 0.4 k+ |
102. 二叉树的层序遍历(Binary Tree Level Order Traversal) | 共 3 种 | 0.4 k+ |
146. LRU 缓存(LRU Cache) | 共 2 种 | 0.5 k+ |
160. 相交链表(Intersection of Two Linked Lists) | 共 2 种 | 0.1 k+ |
200. 岛屿数量(Number of Islands) | 共 4 种 | 0.1 k+ |
206. 反转链表(Reverse Linked List) | 共 3 种 | 1.0 k+ |
215. 数组中的第 K 个最大元素(Kth Largest Element in an Array) | 共 3 种 | 0.5 k+ |
236. 二叉树的最近公共先人(Lowest Common Ancestor of a Binary Tree) | 共 3 种 | 0.1 k+ |
2119. 反转两次的数字(A Number After a Double Reversal) | 共 2 种 | 0.3 k+ |
2120. 执行所有后缀指令(Execution of All Suffix Instructions Staying in a Grid) | 共 1 种 | 0.4 k+ |
2124. 查看是否所有 A 都在 B 之前(Check if All A’s Appears Before All B’s) | 共 4 种 | 0.4 k+ |
2125. 银行中的激光束数量(Number of Laser Beams in a Bank) | 共 3 种 | 0.3 k+ |
2126. 捣毁小行星(Destroying Asteroids) | 共 2 种 | 1.6 k+ |
2129. 将题目首字母大写(Capitalize the Title) | 共 2 种 | 0.6 k+ |
2130. 链表最大孪生和(Maximum Twin Sum of a Linked List) | 共 2 种 | 0.6 k+ |
2133. 查看是否每一行每一列都蕴含全副整数(Check if Every Row and Column Contains All Numbers) | 共 1 种 | 0.6 k+ |
2 博主简介
码农三少,一个致力于编写 极简、但齐全题解(算法 )的博主。
专一于 一题多解、结构化思维,欢送一起刷穿 LeetCode ~