本文主要记录了博主的 Leetcode 算法刷题记录,方便以后查询复习。
链表
相交链表
LeetCode 原题链接:160. 相交链表
哈希表存储遍历的节点,然后进行操作。第二种方法技巧性比较强,利用路径长度相同会回到相交的点的做法来求解。
1/**2 * Definition for singly-linked list.3 * function ListNode(val) {4 * this.val = val;5 * this.next = null;6 * }7 */8
9/**10 * @param {ListNode} headA11 * @param {ListNode} headB12 * @return {ListNode}13 */14const getIntersectionNode = (headA, headB) => {15 const set = new Set();16 while (headA) {17 set.add(headA);18 headA = headA.next;19 }20 while (headB) {21 if (set.has(headB)) {22 return headB;23 } else {24 headB = headB.next;25 }26 }27 return null;28};29
30/**31 * Definition for singly-linked list.32 * function ListNode(val) {33 * this.val = val;34 * this.next = null;35 * }36 */37
38/**39 * @param {ListNode} headA40 * @param {ListNode} headB41 * @return {ListNode}42 */43const getIntersectionNode = (headA, headB) => {44 if (!headA || !headB) {45 return null;46 }47 let p1 = headA,48 p2 = headB;49 while (p1 !== p2) {50 p1 = p1 ? p1.next : headB;51 p2 = p2 ? p2.next : headA;52 }53 return p1;54};55
56// 测试用例,写的满头大汗,还挺多坑的57class ListNode {58 constructor(val) {59 this.val = val;60 this.next = null;61 }62}63
64const p1 = new ListNode();65const p2 = new ListNode();66let temp = p1;67for (let i = 0; i < 5; i++) {68 temp.next = new ListNode(i);69 temp = temp.next;70}71temp = p2;72for (let i = 0; i < 2; i++) {73 temp.next = new ListNode(i + 10);74 temp = temp.next;75}76
77let temp0 = p1;78for (let i = 0; i < 3; i++) {79 temp0 = temp0.next;80}81temp.next = temp0;82
83console.dir(p1, { depth: null });84console.dir(p2, { depth: null });85console.log(getIntersectionNode(p1.next, p2.next));反转链表
LeetCode 原题链接:206. 反转链表
循环和递归,递归比较难以理解,参考意义不是很大。
1/**2 * Definition for singly-linked list.3 * function ListNode(val, next) {4 * this.val = (val===undefined ? 0 : val)5 * this.next = (next===undefined ? null : next)6 * }7 */8/**9 * @param {ListNode} head10 * @return {ListNode}11 */12const reverseList = (head) => {13 const newHead = new ListNode();14 while (head) {15 const nextEl = head.next;16 head.next = newHead.next;17 newHead.next = head;18 head = nextEl;19 }20 return newHead.next;21};22
23/**24 * Definition for singly-linked list.25 * function ListNode(val, next) {26 * this.val = (val===undefined ? 0 : val)27 * this.next = (next===undefined ? null : next)28 * }29 */30/**31 * @param {ListNode} head32 * @return {ListNode}33 */34const reverseList = (head) => {35 if (!head || !head.next) {36 return head;37 }38 const newHead = reverseList(head.next);39 head.next.next = head;40 head.next = null;41 return newHead;42};43
44class ListNode {45 constructor(val) {46 this.val = val;47 this.next = null;48 }49}50
51const p1 = new ListNode();52let temp = p1;53
54for (let i = 0; i < 5; i++) {55 temp.next = new ListNode(i);56 temp = temp.next;57}58
59console.dir(reverseList(p1.next), { depth: null });回文链表
LeetCode 原题链接:234. 回文链表
将值放在数组中然后进行判断
1/**2 * Definition for singly-linked list.3 * function ListNode(val, next) {4 * this.val = (val===undefined ? 0 : val)5 * this.next = (next===undefined ? null : next)6 * }7 */8/**9 * @param {ListNode} head10 * @return {boolean}11 */12const isPalindrome = (head) => {13 const valArr = [];14 while (head) {15 valArr.push(head.val);16 head = head.next;17 }18 let i = 0,19 j = valArr.length - 1;20 while (i < j) {21 if (valArr[i++] !== valArr[j--]) {22 return false;23 }24 }25 return true;26};27
28class ListNode {29 constructor(val) {30 this.val = val;31 this.next = null;32 }33}34
35const p1 = new ListNode();36let temp = p1;37
38for (let i = 0; i < 5; i++) {39 temp.next = new ListNode(Math.abs(i - 2));40 temp = temp.next;41}42
43console.dir(isPalindrome(p1.next), { depth: null });环形链表
LeetCode 原题链接:141. 环形链表
哈希表与快慢指针,无需多言。🥰
1/**2 * Definition for singly-linked list.3 * function ListNode(val) {4 * this.val = val;5 * this.next = null;6 * }7 */8
9/**10 * @param {ListNode} head11 * @return {boolean}12 */13const hasCycle = (head) => {14 if (!head) {15 return false;16 }17 const set = new WeakSet();18 let slow = head,19 fast = head.next;20 while (fast) {21 set.add(slow);22 if (set.has(fast)) {23 return true;24 }25 slow = slow.next;26 fast = fast.next?.next;27 }28 return false;29};30
31/**32 * Definition for singly-linked list.33 * function ListNode(val) {34 * this.val = val;35 * this.next = null;36 * }37 */38
39/**40 * @param {ListNode} head41 * @return {boolean}42 */43const hasCycle = (head) => {44 if (!head) {45 return false;46 }47 let slow = head,48 fast = head.next;49 while (fast) {50 slow = slow.next;51 fast = fast.next?.next;52 if (slow === fast) {53 return true;54 }55 }56 return false;57};58
59class ListNode {60 constructor(val) {61 this.val = val;62 this.next = null;63 }64}65
66const p1 = new ListNode();67let temp = p1;68for (let i = 0; i < 5; i++) {69 temp.next = new ListNode(i);70 temp = temp.next;71}72temp.next = p1.next;73
74console.dir(hasCycle(p1.next), { depth: null });环形链表 Ⅱ
LeetCode 原题链接:142. 环形链表 Ⅱ
哈希表与快慢指针求解,第二种方法技巧性比较强,参考性不是很高。
1/**2 * Definition for singly-linked list.3 * function ListNode(val) {4 * this.val = val;5 * this.next = null;6 * }7 */8
9/**10 * @param {ListNode} head11 * @return {ListNode}12 */13const detectCycle = (head) => {14 const set = new WeakSet();15 let p = head;16 while (p) {17 if (set.has(p)) {18 return p;19 }20 set.add(p);21 p = p.next;22 }23 return null;24};25
26/**27 * Definition for singly-linked list.28 * function ListNode(val) {29 * this.val = val;30 * this.next = null;31 * }32 */33
34/**35 * @param {ListNode} head36 * @return {ListNode}37 */38const detectCycle = (head) => {39 if (head === null) {40 return null;41 }42 let slow = head,43 fast = head;44 while (fast !== null) {45 slow = slow.next;46 if (fast.next !== null) {47 fast = fast.next.next;48 } else {49 return null;50 }51 if (fast === slow) {52 let ptr = head;53 while (ptr !== slow) {54 ptr = ptr.next;55 slow = slow.next;56 }57 return ptr;58 }59 }60 return null;61};62
63class ListNode {64 constructor(val) {65 this.val = val;66 this.next = null;67 }68}69
70const p1 = new ListNode();71let temp = p1;72for (let i = 0; i < 5; i++) {73 temp.next = new ListNode(i);74 temp = temp.next;75}76temp.next = p1.next;77
78const p2 = new ListNode();79temp = p2;80for (let i = 0; i < 5; i++) {81 temp.next = new ListNode(i + 10);82 temp = temp.next;83}84temp.next = p1.next;85
86console.dir(p2.next, { depth: null });87console.dir(detectCycle(p2.next), { depth: null });合并两个有序链表
LeetCode 原题链接:21. 合并两个有序链表
有递归和循环两种写法。
1/**2 * Definition for singly-linked list.3 * function ListNode(val, next) {4 * this.val = (val===undefined ? 0 : val)5 * this.next = (next===undefined ? null : next)6 * }7 */8/**9 * @param {ListNode} list110 * @param {ListNode} list211 * @return {ListNode}12 */13const mergeTwoLists = (list1, list2) => {14 if (!list1) {15 return list2;16 }17 if (!list2) {18 return list1;19 }20 if (list1.val < list2.val) {21 list1.next = mergeTwoLists(list1.next, list2);22 return list1;23 } else {24 list2.next = mergeTwoLists(list1, list2.next);25 return list2;26 }27};28
29/**30 * Definition for singly-linked list.31 * function ListNode(val, next) {32 * this.val = (val===undefined ? 0 : val)33 * this.next = (next===undefined ? null : next)34 * }35 */36/**37 * @param {ListNode} list138 * @param {ListNode} list239 * @return {ListNode}40 */41const mergeTwoLists = (list1, list2) => {42 const dummy = new ListNode();43 let temp = dummy;44 while (list1 && list2) {45 if (list1.val < list2.val) {46 temp.next = list1;47 list1 = list1.next;48 } else {49 temp.next = list2;50 list2 = list2.next;51 }52 temp = temp.next;53 }54 temp.next = list1 || list2;55 return dummy.next;56};57
58class ListNode {59 constructor(val) {60 this.val = val;61 this.next = null;62 }63}64
65const p1 = new ListNode();66let temp = p1;67for (let i = 0; i < 5; i++) {68 temp.next = new ListNode(i * 2);69 temp = temp.next;70}71
72const p2 = new ListNode();73temp = p2;74for (let i = 0; i < 5; i++) {75 temp.next = new ListNode(i * 2 + 1);76 temp = temp.next;77}78
79console.dir(p1.next, { depth: null });80console.dir(p2.next, { depth: null });81console.dir(mergeTwoLists(p1.next, p2.next), { depth: null });两数相加
LeetCode 原题链接:2. 两数相加
注意进位的处理与归零,其他的都比较简单,思路正确照着写就行。
1/**2 * Definition for singly-linked list.3 * function ListNode(val, next) {4 * this.val = (val===undefined ? 0 : val)5 * this.next = (next===undefined ? null : next)6 * }7 */8/**9 * @param {ListNode} l110 * @param {ListNode} l211 * @return {ListNode}12 */13const addTwoNumbers = (l1, l2) => {14 let head = null,15 tail = null;16 let carry = 0;17 while (l1 || l2 || carry) {18 const n1 = l1 ? l1.val : 0;19 const n2 = l2 ? l2.val : 0;20 const sum = n1 + n2 + carry;21 if (!head) {22 head = tail = new ListNode(sum % 10);23 } else {24 tail.next = new ListNode(sum % 10);25 tail = tail.next;26 }27 carry = Math.floor(sum / 10);28 if (l1) {29 l1 = l1.next;30 }31 if (l2) {32 l2 = l2.next;33 }34 }35 return head;36};37
38class ListNode {39 constructor(val) {40 this.val = val;41 this.next = null;42 }43}44
45const p1 = new ListNode();46let temp = p1;47for (let i = 0; i < 5; i++) {48 temp.next = new ListNode(i * 2);49 temp = temp.next;50}51
52const p2 = new ListNode();53temp = p2;54for (let i = 0; i < 5; i++) {55 temp.next = new ListNode(i * 2 + 1);56 temp = temp.next;57}58
59console.dir(p1.next, { depth: null });60console.dir(p2.next, { depth: null });61console.dir(addTwoNumbers(p1.next, p2.next), { depth: null });删除链表的倒数第 N 个节点
LeetCode 原题链接:19. 删除链表的倒数第 N 个结点
采用计算链表长度或者双指针进行求解
1/**2 * Definition for singly-linked list.3 * function ListNode(val, next) {4 * this.val = (val===undefined ? 0 : val)5 * this.next = (next===undefined ? null : next)6 * }7 */8/**9 * @param {ListNode} head10 * @param {number} n11 * @return {ListNode}12 */13const removeNthFromEnd = (head, n) => {14 let length = 0,15 temp = head;16 const newHead = new ListNode(0, head);17 while (temp) {18 length++;19 temp = temp.next;20 }21 temp = newHead;22 for (let i = 0; i < length - n; i++) {23 temp = temp.next;24 }25 temp.next = temp.next.next;26 return newHead.next;27};28
29class ListNode {30 constructor(val, next) {31 this.val = val;32 this.next = next;33 }34}35
36const p1 = new ListNode();37let temp = p1;38for (let i = 0; i < 5; i++) {39 temp.next = new ListNode(i);40 temp = temp.next;41}42
43console.dir(p1.next, { depth: null });44console.dir(removeNthFromEnd(p1.next, 2), { depth: null });两两交换链表中的节点
LeetCode 原题链接:24. 两两交换链表中的节点
注意指针需要用temp.next.next,便于直接删除。
1/**2 * Definition for singly-linked list.3 * function ListNode(val, next) {4 * this.val = (val===undefined ? 0 : val)5 * this.next = (next===undefined ? null : next)6 * }7 */8/**9 * @param {ListNode} head10 * @return {ListNode}11 */12const swapPairs = (head) => {13 const newHead = new ListNode(0, head);14 let temp = newHead;15 while (temp.next?.next) {16 const firstNode = temp.next;17 const SecondNode = temp.next.next;18 const next = SecondNode.next;19 temp.next = SecondNode;20 SecondNode.next = firstNode;21 firstNode.next = next;22 temp = firstNode;23 }24 return newHead.next;25};26
27class ListNode {28 constructor(val, next) {29 this.val = val;30 this.next = next;31 }32}33
34const p1 = new ListNode();35let temp = p1;36for (let i = 0; i < 5; i++) {37 temp.next = new ListNode(i);38 temp = temp.next;39}40
41console.dir(p1.next, { depth: null });42console.dir(swapPairs(p1.next), { depth: null });k 个一组翻转链表
LeetCode 原题链接:25. k 个一组翻转链表
该题思路比较简单,但处理情况比较繁琐,十分考量面试者的代码设计能力,推荐将可以翻转的判断与翻转函数书写,同时需要注意翻转后的链表需要连接回原来的链表,所以需要保留上一链表的节点,所以翻转的时候推荐使用temp.next进行翻转。
1/**2 * Definition for singly-linked list.3 * function ListNode(val, next) {4 * this.val = (val===undefined ? 0 : val)5 * this.next = (next===undefined ? null : next)6 * }7 */8/**9 * @param {ListNode} head10 * @param {number} k11 * @return {ListNode}12 */13const reverseKGroup = (head, k) => {14 const canReverse = (node) => {15 let count = 0;16 while (node) {17 count++;18 node = node.next;19 if (count === k) {20 return true;21 }22 }23 return false;24 };25 const reverse = (node) => {26 const newHead = new ListNode();27 const tail = node;28 for (let i = 0; i < k; i++) {29 const next = node.next;30 node.next = newHead.next;31 newHead.next = node;32 node = next;33 }34 tail.next = node;35 return newHead.next;36 };37 const newHead = new ListNode(0, head);38 let temp = newHead;39 while (canReverse(temp.next)) {40 const tail = temp.next;41 temp.next = reverse(temp.next);42 temp = tail;43 }44 return newHead.next;45};46
47class ListNode {48 constructor(val, next) {49 this.val = val;50 this.next = next;51 }52}53
54const p1 = new ListNode();55let temp = p1;56for (let i = 0; i < 5; i++) {57 temp.next = new ListNode(i);58 temp = temp.next;59}60
61console.dir(p1.next, { depth: null });62console.dir(reverseKGroup(p1.next, 3), { depth: null });随机链表的复制
LeetCode 原题链接:138. 随机链表的复制
采取哈希表存储原链表与复制之后链表之间节点的对应关系,从而实现复制功能,还可以通过递归实现,但基本思路大致相同
1/**2 * // Definition for a Node.3 * function Node(val, next, random) {4 * this.val = val;5 * this.next = next;6 * this.random = random;7 * };8 */9
10/**11 * @param {Node} head12 * @return {Node}13 */14const copyRandomList = (head, map = new WeakMap()) => {15 if (!head) {16 return head;17 }18 if (!map.has(head)) {19 map.set(head, new Node(head.val));20 Object.assign(map.get(head), {21 next: copyRandomList(head.next, map),22 random: copyRandomList(head.random, map),23 });24 }25 return map.get(head);26};27
28/**29 * // Definition for a Node.30 * function Node(val, next, random) {31 * this.val = val;32 * this.next = next;33 * this.random = random;34 * };35 */36
37/**38 * @param {Node} head39 * @return {Node}40 */41const copyRandomList = (head) => {42 const newHead = new Node();43 let temp = newHead,44 temp0 = head;45 const map = new WeakMap();46 while (temp0) {47 temp.next = new Node(temp0.val);48 map.set(temp0, temp.next);49 temp0 = temp0.next;50 temp = temp.next;51 }52 temp = newHead.next;53 temp0 = head;54 while (temp0) {55 const random = temp0.random;56 if (random) {57 temp.random = map.get(random);58 } else {59 temp.random = random;60 }61 temp = temp.next;62 temp0 = temp0.next;63 }64 return newHead.next;65};排序链表
LeetCode 原题链接:148. 排序链表
使用归并排序的思路,求解,左闭右开,同时注意fast指针需要严格遵守fast !== tail的规则来使用。
1/**2 * Definition for singly-linked list.3 * function ListNode(val, next) {4 * this.val = (val===undefined ? 0 : val)5 * this.next = (next===undefined ? null : next)6 * }7 */8/**9 * @param {ListNode} head10 * @return {ListNode}11 */12const sortList = (head) => mergeSort(head, null);13
14const mergeSort = (head, tail) => {15 if (!head) {16 return null;17 }18
19 if (head.next === tail) {20 head.next = null;21 return head;22 }23
24 let slow = head,25 fast = head;26 while (fast !== tail) {27 slow = slow.next;28 fast = fast.next;29 if (fast !== tail) {30 fast = fast.next;31 }32 }33 return mergeTwoLists(mergeSort(head, slow), mergeSort(slow, tail));34};35
36const mergeTwoLists = (p1, p2) => {37 const dummy = new ListNode();38 let temp = dummy;39 while (p1 && p2) {40 if (p1.val < p2.val) {41 temp.next = p1;42 p1 = p1.next;43 } else {44 temp.next = p2;45 p2 = p2.next;46 }47 temp = temp.next;48 }49 temp.next = p1 || p2;50 return dummy.next;51};52
53class ListNode {54 constructor(val, next) {55 this.val = val === undefined ? 0 : val;56 this.next = next === undefined ? null : next;57 }58}59
60const p1 = new ListNode();61let temp = p1;62for (let i = 0; i < 5; i++) {63 temp.next = new ListNode(Math.floor(Math.random() * 5));64 temp = temp.next;65}66console.dir(p1.next, { depth: null });67console.dir(mergeSort(p1.next, null), { depth: null });合并 k 个升序链表
LeetCode 原题链接:23. 合并 k 个升序链表
分治与归并排序,掌握思路就比较简单。
1/**2 * Definition for singly-linked list.3 * function ListNode(val, next) {4 * this.val = (val===undefined ? 0 : val)5 * this.next = (next===undefined ? null : next)6 * }7 */8/**9 * @param {ListNode[]} lists10 * @return {ListNode}11 */12const mergeKLists = (lists) => {13 if (!lists || lists.length === 0) {14 return null;15 }16 if (lists.length === 1) {17 return lists[0];18 }19 if (lists.length === 2) {20 return merge(lists[0], lists[1]);21 }22 const mid = Math.floor(lists.length / 2);23 return merge(mergeKLists(lists.slice(0, mid)), mergeKLists(lists.slice(mid)));24};25
26const merge = (l1, l2) => {27 if (!l1) {28 return l2;29 }30 if (!l2) {31 return l1;32 }33 if (l1.val < l2.val) {34 l1.next = merge(l1.next, l2);35 return l1;36 } else {37 l2.next = merge(l1, l2.next);38 return l2;39 }40};LRU 算法
LeetCode 原题链接:146. LRU 缓存
双向链表加上哈希表解决,算法不难,重点是了解其基本思想,注意过量操作需要删除节点。
1class Node {2 constructor(key, val) {3 this.key = key;4 this.val = val;5 this.pre = null;6 this.next = null;7 }8}9
10class LRUCache {11 constructor(size) {12 this.size = size;13 this.dummy = new Node();14 this.dummy.next = this.dummy;15 this.dummy.pre = this.dummy;16 this.map = new Map();17 }18
19 addFront(el) {20 el.next = this.dummy.next;21 this.dummy.next = el;22 el.pre = this.dummy;23 el.next.pre = el;24 }25
26 delete(el) {27 el.pre.next = el.next;28 el.next.pre = el.pre;29 }30
31 put(key, val) {32 if (this.map.has(key)) {33 const el = this.map.get(key);34 el.val = val;35 this.delete(el);36 this.addFront(el);37 } else {38 const el = new Node(key, val);39 this.map.set(key, el);40 this.addFront(el);41 if (this.map.size > this.size) {42 const el = this.dummy.pre;43 this.map.delete(el.key);44 this.delete(el);45 }46 }47 }48
49 get(key) {50 if (!this.map.has(key)) {51 return -1;52 } else {53 const el = this.map.get(key);54 this.delete(el);55 this.addFront(el);56 return el.val;57 }58 }59}二叉树
二叉树的前序遍历
LeetCode 原题链接:144. 二叉树的前序遍历
可采用递归和迭代的两种方式,详细理解一下前序遍历迭代的套路。
- 维护一个结果
res与栈stack。 - 采用
while循环循环压入栈,判断条件为root || stack.length。 - 与中序遍历的区别在于在内部
while循环中需要推入res数组,而不是在外部推入。 - 注意在循环向左压入数字,栈需要更新
root,而不是新建一个变量。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {number[]}12 */13const preorderTraversal = (root) => {14 const res = [];15 const dfs = (root) => {16 if (!root) {17 return;18 }19 res.push(root.val);20 dfs(root.left);21 dfs(root.right);22 };23 dfs(root);24 return res;25};26
27/**28 * Definition for a binary tree node.29 * function TreeNode(val, left, right) {30 * this.val = (val===undefined ? 0 : val)31 * this.left = (left===undefined ? null : left)32 * this.right = (right===undefined ? null : right)33 * }34 */35/**36 * @param {TreeNode} root37 * @return {number[]}38 */39const preorderTraversal = (root) => {40 const stack = [],41 res = [];42 while (root || stack.length) {43 while (root) {44 res.push(root.val);45 stack.push(root.right);46 root = root.left;47 }48 root = stack.pop();49 }50 return res;51};二叉树的中序遍历
LeetCode 原题链接:94. 二叉树的中序遍历
可采用递归和迭代的两种方式,详细理解一下中序遍历迭代的套路。
- 维护一个结果
res与栈stack。 - 采用
while循环循环压入栈,判断条件为root || stack.length。 - 注意在循环向左压入数字,栈需要更新
root,而不是新建一个变量。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {number[]}12 */13const inorderTraversal = (root) => {14 const res = [];15 const step = (root) => {16 if (!root) {17 return null;18 }19 step(root.left);20 res.push(root.val);21 step(root.right);22 };23 step(root);24 return res;25};26
27/**28 * Definition for a binary tree node.29 * function TreeNode(val, left, right) {30 * this.val = (val===undefined ? 0 : val)31 * this.left = (left===undefined ? null : left)32 * this.right = (right===undefined ? null : right)33 * }34 */35/**36 * @param {TreeNode} root37 * @return {number[]}38 */39const inorderTraversal = (root) => {40 const res = [];41 const stack = [];42 while (root || stack.length) {43 while (root) {44 stack.push(root);45 root = root.left;46 }47 root = stack.pop();48 res.push(root.val);49 root = root.right;50 }51 return res;52};二叉树的后序遍历
LeetCode 原题链接:145. 二叉树的后序遍历
可采用递归和迭代的两种方式,详细理解一下后序遍历迭代的套路。
- 维护一个结果
res与栈stack。 - 采用
while循环循环压入栈,判断条件为root || stack.length。 - 注意在循环向左压入数字,栈需要更新
root,而不是新建一个变量。 - 注意与中序遍历不同的是需要将父节点推入
stack同时在“触底”的时候记录right变量,防止再一次回溯。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {number[]}12 */13const postorderTraversal = (root) => {14 const res = [];15 const dfs = (root) => {16 if (!root) {17 return;18 }19 dfs(root.left);20 dfs(root.right);21 res.push(root.val);22 };23 dfs(root);24 return res;25};26
27/**28 * Definition for a binary tree node.29 * function TreeNode(val, left, right) {30 * this.val = (val===undefined ? 0 : val)31 * this.left = (left===undefined ? null : left)32 * this.right = (right===undefined ? null : right)33 * }34 */35/**36 * @param {TreeNode} root37 * @return {number[]}38 */39const postorderTraversal = (root) => {40 const res = [],41 stack = [];42 let prev = null;43 while (root || stack.length) {44 while (root) {45 stack.push(root);46 root = root.left;47 }48 root = stack.pop();49 if (root.right === null || root.right === prev) {50 res.push(root.val);51 prev = root;52 root = null;53 } else {54 stack.push(root);55 root = root.right;56 }57 }58 return res;59};二叉树的最大深度
LeetCode 原题链接:104. 二叉树的最大深度
采取递归的思路求解,推荐使用回溯算法,即每个节点从叶子节点开始回溯,每次都返回当前节点左右子节点的最大深度加一,最后返回根节点的最大深度。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {number}12 */13const maxDepth = (root) => {14 if (!root) {15 return 0;16 }17 const left = maxDepth(root.left);18 const right = maxDepth(root.right);19 return Math.max(left, right) + 1;20};21
22/**23 * Definition for a binary tree node.24 * function TreeNode(val, left, right) {25 * this.val = (val===undefined ? 0 : val)26 * this.left = (left===undefined ? null : left)27 * this.right = (right===undefined ? null : right)28 * }29 */30/**31 * @param {TreeNode} root32 * @return {number}33 */34const maxDepth = (root) => {35 let max = 0;36 const step = (root, depth = 0) => {37 if (!root) {38 max = Math.max(max, depth);39 return;40 }41 step(root.left, depth + 1);42 step(root.right, depth + 1);43 };44 step(root);45 return max;46};翻转二叉树
LeetCode 原题链接:226. 翻转二叉树
也是同样的回溯思想,叶子节点开始反转,一直反转到根节点,核心思路为先递归到叶子节点然后一步步返回。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {TreeNode}12 */13const invertTree = (root) => {14 if (!root) {15 return root;16 }17 const left = invertTree(root.left);18 const right = invertTree(root.right);19 root.left = right;20 root.right = left;21 return root;22};对称二叉树
LeetCode 原题链接:101. 对称二叉树
初看这个题目或许比较复杂,但简而言之还是按照深度一层层比较,掌握技巧后就比较简单,注意的是判断条件和递归和迭代的实现思路的细微区别。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {boolean}12 */13const isSymmetric = (root) => {14 const step = (p, q) => {15 if (!p && !q) {16 return true;17 }18 if (!p || !q) {19 return false;20 }21 return p.val === q.val && step(p.left, q.right) && step(p.right, q.left);22 };23 return step(root.left, root.right);24};25
26/**27 * Definition for a binary tree node.28 * function TreeNode(val, left, right) {29 * this.val = (val===undefined ? 0 : val)30 * this.left = (left===undefined ? null : left)31 * this.right = (right===undefined ? null : right)32 * }33 */34/**35 * @param {TreeNode} root36 * @return {boolean}37 */38const isSymmetric = (root) => {39 const queue = [root.left, root.right];40 while (queue.length) {41 const p = queue.shift();42 const q = queue.shift();43
44 if (!p && !q) {45 continue;46 }47 if (!p || !q || p.val !== q.val) {48 return false;49 }50
51 queue.push(p.left, q.right, p.right, q.left);52 }53 return true;54};二叉树的直径
LeetCode 原题链接:543. 二叉树的直径
由二叉树的最大深度稍加改进而来,还是一样,先递归到子节点,然后回溯返回。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {number}12 */13const diameterOfBinaryTree = (root) => {14 let maxD = 0;15 const dfs = (root) => {16 if (!root) {17 return 0;18 }19 const left = dfs(root.left);20 const right = dfs(root.right);21 maxD = Math.max(maxD, left + right);22 return Math.max(left, right) + 1;23 };24 dfs(root);25 return maxD;26};二叉树的层序遍历
LeetCode 原题链接:102. 二叉树的层序遍历
层序遍历属于广度优先遍历,与深度优先遍历不同,广度优先遍历一般使用队列与循环完成。不需要二维数组,每次遍历都清空queue。
这个算法有两个需要注意的点
- 只有值不为空的节点才能推入下一次需要遍历的队列。
- 注意当下一次需要遍历的队列为空的时候,不能推入,防止死循环。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {number[][]}12 */13const levelOrder = (root) => {14 if (!root) {15 return [];16 }17
18 const queue = [root];19 const res = [];20
21 while (queue.length) {22 const arr = [];23 const resArr = [];24 while (queue.length) {25 const node = queue.shift();26 resArr.push(node.val);27 if (node.left) {28 arr.push(node.left);29 }30 if (node.right) {31 arr.push(node.right);32 }33 }34 queue.push(...arr);35 res.push(resArr);36 }37 return res;38};将有序数组转化为二叉搜索树
LeetCode 原题链接:108. 将有序数组转换为二叉搜索树
查看二叉搜索树的详细解释
当然可以。二叉搜索树(Binary Search Tree,简称 BST),也称为二叉查找树或二叉排序树,是一种特殊的二叉树。它具有以下性质:
-
有序性:对于树中的任意一个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。这意味着所有的元素能够通过比较操作被明确地排序。
-
递归性质:BST 的左子树和右子树也都是二叉搜索树。这意味着 BST 的定义是递归的,我们可以递归地在子树中进行查找和其他操作。
-
无重复值:在 BST 中,每个元素必须是唯一的,因为树的定义不允许含有相同值的节点。
二叉搜索树的主要优势在于,它结合了链表和数组的优点:链表的快速插入和删除操作,以及数组的快速查找性能。在平均情况下,查找、插入和删除操作的时间复杂度都是 O(logn) ,其中 n 是树中节点的数量。然而,在最坏的情况下,如果树变得不平衡,这些操作的时间复杂度可能会退化到 O(n) 。
二叉搜索树在计算机科学中应用广泛,特别是在那些需要频繁查找、插入和删除数据的场景中,如数据库和文件系统。
采用二分法将有序数组转化为二叉搜索树,判断条件与二分法基本相同,有着相同的边界处理情况。
left = 0, right = nums.length - 1对应low = 0, high = nums.length - 1left > right对应low <= high
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {number[]} nums11 * @return {TreeNode}12 */13const sortedArrayToBST = (nums) => {14 const step = (left, right) => {15 if (left > right) {16 return null;17 }18 const mid = Math.floor((left + right) / 2);19 const root = new TreeNode(nums[mid]);20 root.left = step(left, mid - 1);21 root.right = step(mid + 1, right);22 return root;23 };24 return step(0, nums.length - 1);25};验证二叉搜索树
LeetCode 原题链接:98. 验证二叉搜索树
一种方式是采用上下界递归求解,注意左右节点上下界的选取,以及在JS中正负Infinity的使用。另一种方法则是利用二叉搜索树的中序遍历是升序序列来进行判断,可采用递归和循环两种方式,循环方式代码更加优雅一些。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {boolean}12 */13const isValidBST = (root) => {14 const step = (root, lower, upper) => {15 if (!root) {16 return true;17 }18 if (root.val <= lower || root.val >= upper) {19 return false;20 }21 return (22 step(root.left, lower, root.val) && step(root.right, root.val, upper)23 );24 };25 return step(root, -Infinity, Infinity);26};27
28/**29 * Definition for a binary tree node.30 * function TreeNode(val, left, right) {31 * this.val = (val===undefined ? 0 : val)32 * this.left = (left===undefined ? null : left)33 * this.right = (right===undefined ? null : right)34 * }35 */36/**37 * @param {TreeNode} root38 * @return {boolean}39 */40const isValidBST = (root) => {41 const stack = [];42 let pre = -Infinity;43 while (root || stack.length) {44 while (root) {45 stack.push(root);46 root = root.left;47 }48 root = stack.pop();49 if (pre >= root.val) {50 return false;51 }52 pre = root.val;53 root = root.right;54 }55 return true;56};57
58/**59 * Definition for a binary tree node.60 * function TreeNode(val, left, right) {61 * this.val = (val===undefined ? 0 : val)62 * this.left = (left===undefined ? null : left)63 * this.right = (right===undefined ? null : right)64 * }65 */66/**67 * @param {TreeNode} root68 * @return {boolean}69 */70const isValidBST = (root) => {71 let pre = -Infinity;72 const dfs = (root) => {73 if (!root) {74 return true;75 }76 const left = dfs(root.left);77 if (pre >= root.val) {78 return false;79 }80 pre = root.val;81 const right = dfs(root.right);82 return left && right;83 };84 return dfs(root);85};二叉搜索树中第 k 小的元素
LeetCode 原题链接:230. 二叉搜索树中第 k 小的元素
记住中序遍历的套路直接秒。😍
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @param {number} k12 * @return {number}13 */14const kthSmallest = (root, k) => {15 const stack = [];16 let count = 0;17 while (root || stack.length) {18 while (root) {19 stack.push(root);20 root = root.left;21 }22 root = stack.pop();23 count++;24 if (count === k) {25 return root.val;26 }27 root = root.right;28 }29};二叉树的右视图
LeetCode 原题链接:199. 二叉树的右视图
和层序遍历大致相同,注意基本思路即可。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {number[]}12 */13const rightSideView = (root) => {14 if (!root) {15 return [];16 }17
18 const queue = [root];19 const res = [];20
21 while (queue.length) {22 const arr = [];23 const resArr = [];24 while (queue.length) {25 const node = queue.shift();26 resArr.push(node.val);27 if (node.left) {28 arr.push(node.left);29 }30 if (node.right) {31 arr.push(node.right);32 }33 }34 queue.push(...arr);35 res.push(resArr[resArr.length - 1]);36 }37 return res;38};二叉树展开为链表
LeetCode 原题链接:144. 二叉树展开为链表
采用前序遍历的操作来解决,其实相当于中序遍历迭代写法的变式。因为在内层while循环中已经开始遍历,所以没有弹出栈后往右遍历的步骤。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {void} Do not return anything, modify root in-place instead.12 */13const flatten = (root) => {14 const stack = [];15 const dummy = new TreeNode();16 let temp = dummy;17 while (root || stack.length) {18 while (root) {19 stack.push(root.right);20 temp.right = root;21 temp = temp.right;22 const left = root.left;23 root.left = null;24 root = left;25 }26 root = stack.pop();27 }28 return dummy.right;29};从前序与中序遍历序列构造二叉树
LeetCode 原题链接:105. 从前序与中序遍历序列构造二叉树
这道题技巧性比较强,主要利用了前序数组与中序数组的相关的性质进行求解。进行根元素和左右元素进行分割。其实本质上也是二分,和将有序数组转化为二叉搜索树相同。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {number[]} preorder11 * @param {number[]} inorder12 * @return {TreeNode}13 */14const buildTree = (preorder, inorder) => {15 const map = new Map();16 for (let i = 0; i < inorder.length; i++) {17 map.set(inorder[i], i);18 }19 const step = (p_start, p_end, i_start, i_end) => {20 if (p_start > p_end) {21 return null;22 }23 const mid = map.get(preorder[p_start]);24 const leftNum = mid - i_start;25 const root = new TreeNode(preorder[p_start]);26 root.left = step(p_start + 1, p_start + leftNum, i_start, mid - 1);27 root.right = step(p_start + leftNum + 1, p_end, mid + 1, i_end);28 return root;29 };30 return step(0, preorder.length - 1, 0, inorder.length - 1);31};路径总和 III
LeetCode 原题链接:437. 路径总和 III
不考虑时间复杂度直接深度遍历暴力求解,考虑时间复杂度可以使用前缀和的方式进行求解。和和为-k-的子数组思路大致相同。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @param {number} targetSum12 * @return {number}13 */14const pathSum = (root, targetSum) => {15 const prefix = new Map([[0, 1]]);16
17 const dfs = (root, curr) => {18 if (!root) {19 return 0;20 }21 curr += root.val;22 let ret = prefix.get(curr - targetSum) || 0;23
24 prefix.set(curr, (prefix.get(curr) || 0) + 1);25 ret += dfs(root.left, curr);26 ret += dfs(root.right, curr);27 prefix.set(curr, (prefix.get(curr) || 0) - 1);28
29 return ret;30 };31 return dfs(root, 0);32};33
34/**35 * Definition for a binary tree node.36 * function TreeNode(val, left, right) {37 * this.val = (val===undefined ? 0 : val)38 * this.left = (left===undefined ? null : left)39 * this.right = (right===undefined ? null : right)40 * }41 */42/**43 * @param {TreeNode} root44 * @param {number} targetSum45 * @return {number}46 */47const pathSum = (root, targetSum) => {48 let count = 0;49 const step = (root, sum = 0) => {50 if (!root) {51 return;52 }53 sum += root.val;54 if (targetSum === sum) {55 count++;56 }57 step(root.left, sum);58 step(root.right, sum);59 };60 const preOrder = (root) => {61 if (!root) {62 return;63 }64 step(root);65 preOrder(root.left);66 preOrder(root.right);67 };68 preOrder(root);69 return count;70};二叉树的最近公共祖先
LeetCode 原题链接:236. 二叉树的最近公共祖先
采用递归的方式求解,注意条件之类的判断,当最深的祖先节点被找到之后,之后的节点不会再满足要求。
主要的判断条件(leftSon && rightSon) || ((p.val === root.val || q.val === root.val) && (leftSon || rightSon)),返回leftSon || rightSon || root.val === p.val || root.val === q.val
1/**2 * Definition for a binary tree node.3 * function TreeNode(val) {4 * this.val = val;5 * this.left = this.right = null;6 * }7 */8/**9 * @param {TreeNode} root10 * @param {TreeNode} p11 * @param {TreeNode} q12 * @return {TreeNode}13 */14const lowestCommonAncestor = (root, p, q) => {15 let ans = null;16 const step = (root) => {17 if (!root) {18 return null;19 }20 const leftSon = step(root.left);21 const rightSon = step(root.right);22 if (23 (leftSon && rightSon) ||24 ((root.val === p.val || root.val === q.val) && (leftSon || rightSon))25 ) {26 ans = root;27 }28 return leftSon || rightSon || root.val === p.val || root.val === q.val;29 };30 step(root);31 return ans;32};124. 二叉树的最大路径和
LeetCode 原题链接:124. 二叉树中的最大路径和
在二叉树的直径与最大深度的代码上改良。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @return {number}12 */13const maxPathSum = (root) => {14 let max = -Infinity;15 const step = (root) => {16 if (!root) {17 return 0;18 }19 const left = step(root.left);20 const right = step(root.right);21 const sum = Math.max(left, right) + root.val;22 max = Math.max(max, left + right + root.val);23 return sum > 0 ? sum : 0;24 };25 step(root);26 return max;27};二叉树中和为目标值的路径
LeetCode 原题链接:LCR 153. 二叉树中和为目标值的路径
节省数组空间可采用堆栈弹入或者弹出。
1/**2 * Definition for a binary tree node.3 * function TreeNode(val, left, right) {4 * this.val = (val===undefined ? 0 : val)5 * this.left = (left===undefined ? null : left)6 * this.right = (right===undefined ? null : right)7 * }8 */9/**10 * @param {TreeNode} root11 * @param {number} target12 * @return {number[][]}13 */14const pathTarget = (root, target) => {15 const res = [];16 const step = (root, sum, arr) => {17 if (!root) {18 return;19 }20 sum += root.val;21 arr.push(root.val);22 if (!root.left && !root.right && sum === target) {23 res.push([...arr]);24 }25 step(root.left, sum, arr);26 step(root.right, sum, arr);27 arr.pop();28 };29 step(root, 0, []);30 return res;31};- 文章作者:
- 希亚的西红柿
- 版权声明:
- 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自希亚的西红柿のBlog!
相关推荐
评论
评论加载中…


