Leetcode算法

这道题目能够使用暴力的解法，不过暴力的效率不够高，因而能够采纳二分查找，题目连贯间接给出：https://leetcode.cn/problems/search-insert-position/description/ 通常的整数二分模板是如下这样的： bool check(int x) {/*...*/} // 查看x是否满足某种性质//区间[l, r]被划分成[l, mid]和[mid+1, r]时应用：int bsearch_1(int l, int r) { while(l < r) { int mid = l+r>>1; // 若产生整数溢出 改为 l+(r-l>>1) if(check(mid)) r = mid; //check判断mid是否满足性质 else l = mid+1; }}//区间[l, r]被划分成[l, mid-1]和[mid, r]时应用：int bsearch_2(int l, int r) { while(l < r) { int mid = l+r+1>>1; // 若产生整数溢出 改为 l+(r+1-l>>1) if(check(mid)) l = mid; else r = mid-1; }}能够发现区间边界的划分，不是mid+1就是mid-1，因而这个模板对这道题不太可行，所以独自记录下本题目标二分思路。 二分查找波及的很多的边界条件，逻辑比较简单，就是写不好。置信很多同学对二分查找法中边界条件解决不好。例如到底是while(left < right)还是while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？这里弄不分明次要是因为对区间的定义没有想分明，这就是不变量。要在二分查找的过程中，放弃不变量，这也就是循环不变量 （感兴趣的同学能够查一查）。 ...

题目形容 问题剖析明天这题比较简单，一行代码就解决了，思路其实简略，就是判断下以后数的奇偶性，如果是偶数，那么最小公倍数必定就是数自身；如果是奇数，那么就是两个数的乘积。 当然，还有一个更艰深的做法，就是依据 "最大公约数和最小公倍数的乘积等于两数乘积" 的关系进行求解，通过欧几里得办法求出最大公约数，最小公倍数也就求进去了，然而，针对这个题这就显得有点麻烦了，晓得就好。 代码实现//1. 通过判断奇偶性求解class Solution {public: int smallestEvenMultiple(int n) { return ((n & 1) == 0) ? n : n * 2; }};//2. 通过最大公约数，最小公倍数关系求解class Solution {public: int gcd(int a, int b) { // 求最大公约数 if (a < b) swap(a, b); // 保障a大于等于b while (b != 0) { int r = a % b; a = b; b = r; } return a; } int lcm(int a, int b) { // 求最小公倍数 return a * b / gcd(a, b); } int smallestEvenMultiple(int n) { return lcm(2, n); }};

430. 扁平化多级双向链表写在后面：最近事件比拟多，马上要筹备期末考试了，当初是在温习。而后又有数据库课设和计算机组成原理课设，好多事件要做，还有马上就要考六级口试了，每天都要刷英语题，然而做算法题我是肯定会坚持下去的，心愿大家能够和我一起致力，谢谢大家。原题链接：https://leetcode.cn/problems/...leetcode 430.扁平化多级双向链表题目形容：你会失去一个双链表，其中蕴含的节点有一个下一个指针、一个前一个指针和一个额定的子指针。这个子指针可能指向一个独自的双向链表，也蕴含这些非凡的节点。这些子列表能够有一个或多个本人的子列表，以此类推，以生成如上面的示例所示的多层数据结构给定链表的头节点head,将链表扁平化，以便所有节点都呈现在单层双链表中。让crr是一个带有子列表的节点。子列表中的节点应该呈现在扁平化列表中的curr之后和curr.next之前。返回扁平列表的had。列表中的节点必须将其所有子指针设置为NULL。最开始题目我感觉有点难了解，要看好几遍才能够了解，我倡议你关上链接间接看leetcode外面的题目形容，我这里写的不是很分明。示例： 做题思路深度优先遍历的思维，我这里用的栈来写深度优先遍历，没有用队列，遇到一个节点cur，if(cur->child==NULL)cur=dfs(cur->next); else{ 递归搜寻到孩子节点为头节点的链表的尾部，将这几个点连贯好（这里我用一张图来示意）；}留神：因为是双向链表，要批改连贯的中央有四个。而后t1,t2别离是是孩子链表上的头和尾节点。 代码c++版class Solution {public: Node* dfs(Node* now){ if(now==NULL) return NULL; Node* ans=NULL; if(now->child==NULL){ if(now->next==NULL) return now; ans=dfs(now->next); } else{ Node* t1=now->child; Node* t2=dfs(now->child); Node* t3=now->next; now->child=NULL; now->next=t1; t1->prev=now; t2->next=t3; if(t3==NULL) return t2; else t3->prev=t2; ans=dfs(t3); } return ans; } Node* flatten(Node* head) { dfs(head); return head; }};

235. 二叉搜寻树的最近公共先人题意：(1)所有节点的值都是惟一的。(2)p、q 为不同节点且均存在于给定的二叉搜寻树中。剖析分3种状况：(1) p、q别离在root左右子树中。此时root即为最近公共先人(2) p、q都在左子树中，最近公共先人在左子树中，遍历左子树 (3) p、q都在右子树中，遍历右子树 题解1、递归 class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if((root->val - p->val) * (root->val - q->val) <= 0) return root; if(root->val > p->val) return lowestCommonAncestor(root->left, p, q); else return lowestCommonAncestor(root->right, p, q); }};2、迭代 class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while(1) { if((root->val - p->val) * (root->val - q->val) <= 0) return root; if(root->val > p->val) root = root->left; else root = root->right; } return root; }};236. 二叉树的最近公共先人办法一：递归后序遍历，当遇到节点p或q时返回，故依据返回值得出pq是否在子树中。因为是后序遍历，故第一次碰到节点p,q在节点root的异侧时[包含root==p或q的状况]，节点root即为最近公共先人，则向上返回root。 ...

leetcode 382. 链表随机节点给你一个单链表，随机抉择链表的一个节点，并返回相应的节点值。每个节点被选中的概率一样。 实现 Solution 类：Solution(ListNode head) 应用整数数组初始化对象。int getRandom() 从链表中随机抉择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。 进阶：如果链表十分大且长度未知，该怎么解决？你是否在不应用额定空间的状况下解决此问题？ 办法1 [空间复杂度O(n)]咱们能够在初始化时，用一个数组记录链表中的所有元素，这样随机抉择链表的一个节点，就变成在数组中随机抉择一个元素。应用rand()办法即可。 办法2 [空间复杂度O(1)]应用蓄水池抽样算法：假如有数据流 1, 2, 3, ..., n。怎么在不晓得n的具体值得状况下使得其中某个值m被抽样的概率为1/n呢？ 规定当遍历到m时咱们以1/m的概率获得m，那么最终后果为m的要求是：m+1, m+2, ... , n都不会被抽到，这些概率为m/m+1，m+1/m+2, ..., n-1/n。综上，最终抽获得值为m的概率为1/m × m/m+1 × m+1/m+2 × ... × n-1/n = 1/n。与m后面的值是否被抽样，因为m抽到会笼罩。 长处：蓄水池抽样因为空间小，能够用于大数据流中的随机抽样问题。 代码class Solution {public: ListNode* h; Solution(ListNode* head) { h = head; } int getRandom() { int ans = 0, n = 1; for (ListNode* p = h; p; p = p->next, n++) { if (rand() % n == 0) ans = p->val; } return ans; }};

leetcode 528. 按权重随机抉择给你一个下标从 0 开始 的正整数数组 w，其中 w[i] 代表第 i 个下标的权重。 请你实现一个函数 pickIndex，它能够随机地从范畴 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的概率 为 w[i] / sum(w) 。 例如，对于 w = [1, 3]，筛选下标 0 的概率为 1 / (1 + 3) = 0.25（即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。 rand()Generate random numberReturns a pseudo-random integral number in the range between 0 and RAND_MAX. rand() % n 产生范畴为[0, n)中的随机数。 ...

leetcode 384. 打乱数组给你一个整数数组 nums，设计算法来打乱一个没有反复元素的数组。打乱后，数组的所有排列应该是等可能的。 实现 Solution class:Solution(int[] nums) 应用整数数组 nums 初始化对象int[] reset() 重设数组到它的初始状态并返回int[] shuffle() 返回数组随机打乱后的后果 示例 1：输出["Solution", "shuffle", "reset", "shuffle"][[[1, 2, 3]], [], [], []]输入[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]] 解释Solution solution = new Solution([1, 2, 3]);solution.shuffle(); // 打乱数组 [1,2,3] 并返回后果。任何 [1,2,3]的排列返回的概率应该雷同。例如，返回 [3, 1, 2]solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的后果。例如，返回 [1, 3, 2] 提醒：1 <= nums.length <= 200-106 <= nums[i] <= 106nums 中的所有元素都是 惟一的最多能够调用 5 * 104 次 reset 和 shuffle ...

leetcode 76. 最小笼罩子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 留神：对于 t 中反复字符，咱们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，咱们保障它是惟一的答案。 示例 1：输出：s = "ADOBECODEBANC", t = "ABC"输入："BANC" 应用两个哈希表，ht存字符串t的字符呈现次数。而后遍历字符串s，当某个字符次数还未到t中的次数，则示意该字符是无效字符[可用于笼罩t]。 双指针算加须要指针具备枯燥性，这样工夫复杂度能力为O(n)。枯燥性证实：假如[j, i]之间的字符为涵盖t的一段，则当i往后走到i'，[j, i']必定也涵盖了t。此时j也只能往后走，因为要求的是最小子串。 什么时候j能够往后走：当s[j]呈现次数大于t中的次数时，阐明即便没有s[j]，[j, i]中也至多有了ht[s[j]]个s[j]了，故此时曾经不须要j地位字符。 unordered_map<char, int> hs, ht;string minWindow(string s, string t) { for (char c : t) ht[c]++; string ans; for (int i = 0, j = 0, cnt = 0; i < s.size(); i++) { hs[s[i]]++; if (hs[s[i]] <= ht[s[i]]) cnt++; while (hs[s[j]] > ht[s[j]]) // 不能是>=，因为只有当该字符在hs中冗余了，能力将该字符略过 hs[s[j++]]--; if (cnt == t.size()) { if (ans.empty() || i - j + 1 < ans.size()) ans = s.substr(j, i - j + 1); } } return ans;}leetcode 3. 无反复字符的最长子串 ...

全排列有两种枚举程序：（1）按程序枚举每个地位填哪个数（2）按程序枚举每个数填哪个地位 两种程序都能解，但如果要保障字典序，则须要应用（1）按程序枚举每个地位填哪个数。因为优先思考将小的数放到后面地位。 leetcode 46. 全排列给定一个不含反复数字的数组 nums ，返回其所有可能的全排列。你能够按任意程序返回答案。 示例 1：输出：nums = [1,2,3]输入：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 提醒：1 <= nums.length <= 6-10 <= nums[i] <= 10nums 中的所有整数 互不雷同 计划：采纳（1）按程序枚举每个地位填哪个数 class Solution { List<Integer> path = new ArrayList<>(); List<List<Integer>> ans = new ArrayList<>();; public List<List<Integer>> permute(int[] nums) { dfs(nums, 0, 0); return ans; } // u:坑位，按程序枚举每个坑位填哪个数 public void dfs(int[] nums, int u, int state) { if (u == nums.length) { ans.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { //枚举每个数 if ((state >> i & 1) == 0) { path.add(nums[i]); dfs(nums, u + 1, state + (1 << i)); path.remove(path.size() - 1); } } }}leetcode 47. 全排列 II ...

首先须要应用Floyd 判圈算法（又称龟兔赛跑算法）的快慢指针思维找到环内快慢指针相遇点c。如图所示：假如终点为a，环的入口点为b。终点a到环入口点的间隔为x，环的入口点到快慢指针相遇点间隔为y。 从快慢指针相遇点将慢指针往回倒退y步达到点b，因为快指针速度是慢指针的两倍，故快指针会倒退到c'点，其中b到c'的间隔也为y。即当慢指针走到b点时，快指针的地位在c'。因为慢指针此时走了x步，故快指针从a走2x步达到了c'点。进而等价于快指针从b点走x间隔会走到c'点。 因为bc = bc'，故从c点走x间隔会走到b点。a->b == c->b[当然c到b可能走了不止一圈]。 综上，当快慢指针相遇后，设置两指针p1、p2，p1终点为a，p2终点为c，同时一走一步，当p1和p2相遇，即为环的入口点。p1、p2可重用快慢指针。 public ListNode detectCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) break; } if (fast == null || fast.next == null) return null; slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow;}

大厂算法面试之leetcode精讲11剪枝&回溯视频解说（高效学习）:点击学习目录：1.开篇介绍 2.工夫空间复杂度 3.动静布局 4.贪婪 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.枯燥栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其余类型题 剪枝排除那些不符合条件的分支。进步程序的运行效率。 回溯：一层层递归，尝试搜素答案， 找到答案：返回后果，尝试其余的分支找不到答案：返回上一层，尝试其余分支回溯模版： result = [];function backtrack (path, list) { if (满足条件) { result.push(path); return } for () { // 单层逻辑 backtrack (path, list) // 撤销抉择 重置状态 }}回溯四部曲： 回溯参数终止条件单层递归逻辑抉择其余分支（撤销抉择 重置状态）22. 括号生成 （medium） 办法1:暴力复杂度剖析：工夫复杂度O(2^2n*n)，字符串的长度为2n，每个地位有两种抉择，抉择左或者右括号，验证字符串是否无效复杂度O(n)，剪枝之后会优化，最坏的状况是O(2^2n*n)。空间复杂度O(n),递归次数最多2n 办法2.递归dfs思路：采纳递归，终止条件是字符串的长度等于2n，递归函数传入构建的字符串，左右括号残余多少，每个地位有两种抉择，抉择左或者右括号，这里能够进行剪枝优化，只有右括号的保有数量大于左括号的保有数量，能力选右括号，否则必定不能形成无效括号Js: const generateParenthesis = (n) => { const res = []; // 输入的后果数组 const generate = (str, left, right) => { if (str.length == 2 * n) { // 字符串构建实现 res.push(str); // 将字符串退出res return; // 完结以后递归（完结以后搜寻分支） } if (left > 0) { // 只有左括号有剩，能够选它，持续递归做抉择 generate(str + '(', left - 1, right); } if (right > left) { // 右括号的保有数量大于左括号的保有数量，能力选右括号 generate(str + ')', left, right - 1); } }; generate('', n, n); // 递归的入口，初始字符串是空字符串，初始括号数量都是n return res;};Java: ...

门路问题2021.05.13No.514 自在之路电子游戏“辐射4”中，工作“通向自在”要求玩家达到名为“Freedom Trail Ring”的金属表盘，并应用表盘拼写特定关键词能力开门。给定一个字符串 ring，示意刻在外环上的编码；给定另一个字符串 key，示意须要拼写的关键词。您须要算出可能拼写关键词中所有字符的起码步数。 最后，ring 的第一个字符与12:00方向对齐。您须要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，而后按下核心按钮，以此一一拼写完 key 中的所有字符。 旋转 ring 拼出 key 字符 key[i] 的阶段中： 您能够将 ring 顺时针或逆时针旋转一个地位，计为1步。旋转的最终目标是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。如果字符 key[i] 曾经对齐到12:00方向，您须要按下核心按钮进行拼写，这也将算作 1 步。按完之后，您能够开始拼写 key 的下一个字符（下一阶段）, 直至实现所有拼写。示例：    输出: ring = "godding", key = "gd"输入: 4解释: 对于 key 的第一个字符 'g'，曾经在正确的地位, 咱们只须要1步来拼写这个字符。 对于 key 的第二个字符 'd'，咱们须要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。 当然, 咱们还须要1步进行拼写。 因而最终的输入是 4。提醒： ring 和 key 的字符串长度取值范畴均为 1 至 100；两个字符串中都只有小写字符，并且均可能存在反复字符；字符串 key 肯定能够由字符串 ring 旋转拼出。 起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/freedom-trail著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 计划：/* * @lc app=leetcode.cn id=514 lang=javascript * * [514] 自在之路 */// @lc code=start/** * @param {string} ring * @param {string} key * @return {number} */var findRotateSteps = function(ring, key) { // 用于存储ring中的索引信息 const keyMap = {}; for(let i = 0; i < ring.length; i++) { const k = ring[i]; if(keyMap[k]) { keyMap[k].push(i) } else { keyMap[k] = [i] } } // 缓存用于dfs剪枝 const memo = new Array(ring.length); for(let i = 0; i < ring.length; i++) { memo[i] = new Array(key.length).fill(-1) } // dfs递归 const dfs = ( ringI, keyI ) => { if(keyI == key.length) return 0; // 剪枝 有缓存间接返回缓存的后果 if( memo[ringI][keyI] !== -1 ) return memo[ringI][keyI] const cur = key[keyI]; // 返回的后果 let res = Infinity; for(const targetI of keyMap[cur]) { // 正向地位 let d1 = Math.abs(ringI - targetI), d2 = ring.length - d1; const curMin = Math.min(d1, d2) // 递归的循环不变式 res = Math.min(res, curMin + dfs(targetI, keyI+1)) } memo[ringI][keyI] = res; return res; } return dfs(0,0) + key.length;};动静布局，关键在于找到剪枝优化计划 ...

反转问题2021.02.11No.25 K个一组翻转链表给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最初残余的节点放弃原有程序。   示例： 给你这个链表：1->2->3->4->5 当 k = 2 时，该当返回: 2->1->4->3->5 当 k = 3 时，该当返回: 3->2->1->4->5   阐明： 你的算法只能应用常数的额定空间。你不能只是单纯的扭转节点外部的值，而是须要理论进行节点替换。 起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 计划一：/* * @lc app=leetcode.cn id=25 lang=javascript * * [25] K 个一组翻转链表 */// @lc code=start/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @param {number} k * @return {ListNode} */var reverseKGroup = function(head, k) { // 链表转数组 const list2Arr = head => { const a = [head.val]; while(head.next) {a.push(head.next.val);head = head.next;} return a; } // 数组转链表 const arr2List = arr => { let head = new ListNode(arr[0]); let cur = head; for(let i=1; i < arr.length; i++) { cur.next = new ListNode(arr[i]); cur = cur.next; }; return head; }; // 对k个节点进行数组切割即可 const kReverse = (a,k) => { const r = []; let cnt = 0; while(a.length >= k + cnt) { let tmp = a.slice(cnt, cnt+k); tmp.reverse(); tmp.map( (x)=> r.push(x)); cnt += k; } a.slice(cnt).map( (x)=> r.push(x)); return r; } return arr2List(kReverse(list2Arr(head), k));};计划二：/* * @lc app=leetcode.cn id=25 lang=javascript * * [25] K 个一组翻转链表 */// @lc code=start/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @param {number} k * @return {ListNode} */var reverseKGroup = function(head, k) { let cur = head; let count = 0; // 求k个待反转元素的首节点和尾节点 while(cur != null && count != k){ cur = cur.next; count++; } // 足够k个节点，去反转 if(count == k){ // 递归链接后续k个反转的链表头节点 cur = reverseKGroup(cur,k); while(count != 0){ count--; // 反转链表 let tmp = head.next; head.next = cur; cur = head; head = tmp; } head = cur; } return head;};计划三：/* * @lc app=leetcode.cn id=25 lang=javascript * * [25] K 个一组翻转链表 */// @lc code=start/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @param {number} k * @return {ListNode} */var reverseKGroup = function(head, k) { if(!head) return null; // 反转链表 let reverse = (a,b) => { let pre; let cur = a; let next = b; while(cur != b){ next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } // 反转区间a-b的k个待反转的元素 let a = head; let b = head; for(let i = 0;i < k;i++){ // 有余k个，不须要反转 if(!b) return head; b = b.next; } // 反转前k个元素 let newHead = reverse(a,b); // 递归链接后续反转链表 a.next = reverseKGroup(b,k); return newHead;};计划四：/* * @lc app=leetcode.cn id=25 lang=javascript * * [25] K 个一组翻转链表 */// @lc code=start/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @param {number} k * @return {ListNode} */var reverseKGroup = function(head, k) { let stack = []; let preHead = new ListNode(0); let pre = preHead; // 循环链接后续反转链表 while(true){ let count = 0; let tmp = head; while(tmp && count < k){ stack.push(tmp); tmp = tmp.next; count++; } // 不够k个，间接链接剩下链表返回 if(count != k){ pre.next = head; break; } // 出栈即是反转 while(stack.length > 0){ pre.next = stack.pop(); pre = pre.next; } pre.next = tmp; head = tmp; } return preHead.next;};计划五：/* * @lc app=leetcode.cn id=25 lang=javascript * * [25] K 个一组翻转链表 */// @lc code=start/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @param {number} k * @return {ListNode} */var reverseKGroup = function(head, k) { const myReverse = (head, tail) => { let prev = tail.next; let p = head; while (prev !== tail) { const nex = p.next; p.next = prev; prev = p; p = nex; } return [tail, head]; } const hair = new ListNode(0); hair.next = head; let pre = hair; while (head) { let tail = pre; // 查看残余局部长度是否大于等于 k for (let i = 0; i < k; ++i) { tail = tail.next; if (!tail) { return hair.next; } } const nex = tail.next; [head, tail] = myReverse(head, tail); // 把子链表从新接回原链表 pre.next = head; tail.next = nex; pre = tail; head = tail.next; } return hair.next;};有五种解法：1、利用数组求解，比拟轻便，须要切换成数组再切回来；2、递归相干计划，利用栈、迭代等进行解析；3、利用虚置前节点，将复杂度降到常数级别，很奇妙 ...

遍历问题2020.11.02No.94 二叉树的中序遍历给定一个二叉树，返回它的中序 遍历。 示例: 输出: [1,null,2,3]   1    \     2    /   3 输入: [1,3,2]进阶: 递归算法很简略，你能够通过迭代算法实现吗？ 起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 计划一：/* * @lc app=leetcode.cn id=94 lang=javascript * * [94] 二叉树的中序遍历 */// @lc code=start/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[]} */var inorderTraversal = function(root) { let r = []; // 递归函数 const recurse = root => { // 递归终止条件 if(!root) return; // 先遍历左子树 recurse(root.left); // 遇到终止条件，此时的val是合乎终止条件的值 r.push(root.val); // 再遍历右子树 recurse(root.right); }; recurse(root); return r;};计划二：/* * @lc app=leetcode.cn id=94 lang=javascript * * [94] 二叉树的中序遍历 */// @lc code=start/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[]} */var inorderTraversal = function(root) { const res = []; const stk = []; while (root || stk.length) { while (root) { stk.push(root); root = root.left; } root = stk.pop(); res.push(root.val); root = root.right; } return res;};计划三：/* * @lc app=leetcode.cn id=94 lang=javascript * * [94] 二叉树的中序遍历 */// @lc code=start/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[]} */var inorderTraversal = function(root) { const res = []; let predecessor = null; while (root) { if (root.left) { // predecessor 节点就是以后 root 节点向左走一步，而后始终向右走至无奈走为止 predecessor = root.left; while (predecessor.right && predecessor.right !== root) { predecessor = predecessor.right; } // 让 predecessor 的右指针指向 root，持续遍历左子树 if (!predecessor.right) { predecessor.right = root; root = root.left; } // 阐明左子树曾经拜访完了，咱们须要断开链接 else { res.push(root.val); predecessor.right = null; root = root.right; } } // 如果没有左孩子，则间接拜访右孩子 else { res.push(root.val); root = root.right; } } return res;};计划四：/* * @lc app=leetcode.cn id=94 lang=javascript * * [94] 二叉树的中序遍历 */// @lc code=start/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[]} */var inorderTraversal = function(root) { if (root) { return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)] } else { return [] }}有四种解法：1、利用递归来实现遍历，对于递归的终止条件要解决好，相当于是隐式的栈利用；2、利用栈来显式的执行，能够管制迭代和进行；3、Morris遍历算法：其本质是利用树种大量的null空间，利用线索树来实现链路的线索，该算法的外围是：以后节点记为cur，a、如果cur无左子节点，cur右移 cur = cur.right；b、如果有左子节点，找到cur左子树的最右节点，记为mostright，b1、如果mostright的right为null，让其指向cur，并且cur左移 cur = cur.left；b2、如果mostright的right指向cur，让其指为null，cur右移 cur = cur.right；4、利用js的...的iterable属性，可最简化写法 ...