链表相关
反转链表
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。Leetcode 206
方法一：迭代
javascript
const reverseList = (head) => {
// 创建一个当前指针之前的指针（前指针）指向 null，一个当前指针指向当前节点
let prev = null,
curr = head;
while (curr) {
// 创建一个当前指针之后的指针（后指针）指向下一个节点
const next = curr.next;
// 当前节点的 next 指向前指针的节点
curr.next = prev;
// 前指针指向当前指针的节点（向后移动一位）
prev = curr;
// 当前指针指向后指针的节点（向后移动一位）
curr = next;
}
// 因为终止迭代判定的是当前指针，所以迭代后当前指针指向 null，返回的应该是前指针所指的节点
return prev;
};const reverseList = (head) => {
// 创建一个当前指针之前的指针（前指针）指向 null，一个当前指针指向当前节点
let prev = null,
curr = head;
while (curr) {
// 创建一个当前指针之后的指针（后指针）指向下一个节点
const next = curr.next;
// 当前节点的 next 指向前指针的节点
curr.next = prev;
// 前指针指向当前指针的节点（向后移动一位）
prev = curr;
// 当前指针指向后指针的节点（向后移动一位）
curr = next;
}
// 因为终止迭代判定的是当前指针，所以迭代后当前指针指向 null，返回的应该是前指针所指的节点
return prev;
};方法二：递归
javascript
const reverseList = (head) => {
if (head == null || head.next == null) {
// 1. 如果当前 head 为 null，直接返回 head 不用递归
// 2. 如果当前 head 的下一个节点为 null，说明到了最后一个节点，返回 head 将其当做反转最终完成后的 head
return head;
}
// 将当前 head 的下一个节点放入迭代，得到的是迭代完成后的 head
const newHead = reverseList(head.next);
// 将当前 head 的下一个节点的 next 指向当前 head（反转）
head.next.next = head;
// 将当前 head 的 next 指向 null
head.next = null;
// 返回最终完成后的 head
return newHead;
};const reverseList = (head) => {
if (head == null || head.next == null) {
// 1. 如果当前 head 为 null，直接返回 head 不用递归
// 2. 如果当前 head 的下一个节点为 null，说明到了最后一个节点，返回 head 将其当做反转最终完成后的 head
return head;
}
// 将当前 head 的下一个节点放入迭代，得到的是迭代完成后的 head
const newHead = reverseList(head.next);
// 将当前 head 的下一个节点的 next 指向当前 head（反转）
head.next.next = head;
// 将当前 head 的 next 指向 null
head.next = null;
// 返回最终完成后的 head
return newHead;
};回文链表
给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。 Leetcode 234
方法一：将值复制到数组中后用双指针法
javascript
const isPalindrome = (head) => {
// 1. 将链表复制到数组
const vals = [];
while (head !== null) {
vals.push(head.val);
head = head.next;
}
// 2. 双指针分别从数组两头向中间取数比较
for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
if (vals[i] !== vals[j]) {
return false;
}
}
return true;
};const isPalindrome = (head) => {
// 1. 将链表复制到数组
const vals = [];
while (head !== null) {
vals.push(head.val);
head = head.next;
}
// 2. 双指针分别从数组两头向中间取数比较
for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
if (vals[i] !== vals[j]) {
return false;
}
}
return true;
};方法二：递归
javascript
const isPalindrome = (head) => {
// 创建一个指针指向头部（头指针）
let frontPointer = head;
const recursivelyCheck = (currentNode) => {
// currentNode 为利用递归指向尾部的指针（尾指针）
if (currentNode !== null) {
if (!recursivelyCheck(currentNode.next)) {
// 如果递归过程出现 false，说明已经出现不是回文的情况，直接返回 false
return false;
}
if (currentNode.val !== frontPointer.val) {
// 如果头指针和尾指针不相同，说明不是回文，返回 false
return false;
}
// 如果头指针和尾指针相同，则头指针向后移动一位（尾指针是迭代过程中出现的，此次迭代后会自动向前一位）
frontPointer = frontPointer.next;
}
// 1. 如果尾指针为 null，说明已经到尾部了，返回 true
// 2. 如果尾指针不为 null 却走到这里，说明到目前为止是回文情况，返回 true 使迭代继续
return true;
};
return recursivelyCheck(head);
};const isPalindrome = (head) => {
// 创建一个指针指向头部（头指针）
let frontPointer = head;
const recursivelyCheck = (currentNode) => {
// currentNode 为利用递归指向尾部的指针（尾指针）
if (currentNode !== null) {
if (!recursivelyCheck(currentNode.next)) {
// 如果递归过程出现 false，说明已经出现不是回文的情况，直接返回 false
return false;
}
if (currentNode.val !== frontPointer.val) {
// 如果头指针和尾指针不相同，说明不是回文，返回 false
return false;
}
// 如果头指针和尾指针相同，则头指针向后移动一位（尾指针是迭代过程中出现的，此次迭代后会自动向前一位）
frontPointer = frontPointer.next;
}
// 1. 如果尾指针为 null，说明已经到尾部了，返回 true
// 2. 如果尾指针不为 null 却走到这里，说明到目前为止是回文情况，返回 true 使迭代继续
return true;
};
return recursivelyCheck(head);
};环形链表
给你一个链表的头节点 head，判断链表中是否有环。如果链表中存在环，则返回 true；否则，返回 false。Leetcode 141
方法一、二：两个讨巧解法（只用于开阔眼界，面试慎用）
javascript
// 利用 JSON.stringify() 参数有循环引用会报错的机制
const hasCycle = (head) => {
try {
JSON.stringify(head);
} catch {
return true;
}
return false;
};// 利用 JSON.stringify() 参数有循环引用会报错的机制
const hasCycle = (head) => {
try {
JSON.stringify(head);
} catch {
return true;
}
return false;
};javascript
// 此方法也可以用 Map 或 Set 改写
const hasCycle = (head) => {
while (head) {
if (head.tag) {
// 迭代时如果遇到标签，说明有环
return true;
}
// 为当前节点做上标记
head.tag = true;
// 迭代下一个节点
head = head.next;
}
// 如果迭代完都没有遇到标签，说明没有环
return false;
};// 此方法也可以用 Map 或 Set 改写
const hasCycle = (head) => {
while (head) {
if (head.tag) {
// 迭代时如果遇到标签，说明有环
return true;
}
// 为当前节点做上标记
head.tag = true;
// 迭代下一个节点
head = head.next;
}
// 如果迭代完都没有遇到标签，说明没有环
return false;
};方法三：快慢指针
javascript
const hasCycle = (head) => {
//设置快慢指针
let slow = head,
fast = head;
while (fast && fast.next) {
// 迭代终止条件为快指针走到尾部
// 迭代时，慢指针每次走一步，快指针每次走两步
slow = slow.next;
fast = fast.next.next;
// 如果快慢指针相遇，说明有环
if (slow == fast) {
return true;
}
}
// 1. 如果 head 为 null，则没有环
// 2. 如果迭代完成，说明没有坏
return false;
};const hasCycle = (head) => {
//设置快慢指针
let slow = head,
fast = head;
while (fast && fast.next) {
// 迭代终止条件为快指针走到尾部
// 迭代时，慢指针每次走一步，快指针每次走两步
slow = slow.next;
fast = fast.next.next;
// 如果快慢指针相遇，说明有环
if (slow == fast) {
return true;
}
}
// 1. 如果 head 为 null，则没有环
// 2. 如果迭代完成，说明没有坏
return false;
};排序链表
给你链表的头结点 head，请将其按升序排列并返回排序后的链表。Leetcode 148
方法一：讨巧解法（只用于开阔眼界，面试慎用）
javascript
const sortList = (head) => {
if (!head) return null;
const list = [];
// 迭代将链表打断并装入数组
while (head) {
let nextHead = head.next;
head.next = null;
list.push(head);
head = nextHead;
}
// 数组排序 + 重组
list.sort((a, b) => a.val - b.val).reduce((p, v) => (p.next = v));
return list[0];
};const sortList = (head) => {
if (!head) return null;
const list = [];
// 迭代将链表打断并装入数组
while (head) {
let nextHead = head.next;
head.next = null;
list.push(head);
head = nextHead;
}
// 数组排序 + 重组
list.sort((a, b) => a.val - b.val).reduce((p, v) => (p.next = v));
return list[0];
};方法二：归并排序
javascript
const sortList = (head) => {
if (!head || head.next === null) return head;
// 使用快慢指针找到中间节点
let slow = head,
fast = head.next;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// 将链表分成两半并返回后半部分链表的头节点
let newListHead = slow.next;
slow.next = null;
// 对前后两个链表进行排序
let left = sortList(head);
let right = sortList(newListHead);
// 创建一个节点当头节点
let res = new ListNode(-1);
let newHead = res;
// 将排序好的两个有序链表合并为一个链表
// 合并链表只需要调整指针的指向
while (left !== null && right !== null) {
// 两个链表哪个节点的值小就先指向它，然后被指的链表向后移动一位
if (left.val < right.val) {
newHead.next = left;
left = left.next;
} else {
newHead.next = right;
right = right.next;
}
// 每次迭代向后移动一位
newHead = newHead.next;
}
// 迭代结束是因为有一个链表到头了，那么将另一个接到后面
newHead.next = left === null ? right : left;
// 注意不要返回第一个节点
return res.next;
};const sortList = (head) => {
if (!head || head.next === null) return head;
// 使用快慢指针找到中间节点
let slow = head,
fast = head.next;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// 将链表分成两半并返回后半部分链表的头节点
let newListHead = slow.next;
slow.next = null;
// 对前后两个链表进行排序
let left = sortList(head);
let right = sortList(newListHead);
// 创建一个节点当头节点
let res = new ListNode(-1);
let newHead = res;
// 将排序好的两个有序链表合并为一个链表
// 合并链表只需要调整指针的指向
while (left !== null && right !== null) {
// 两个链表哪个节点的值小就先指向它，然后被指的链表向后移动一位
if (left.val < right.val) {
newHead.next = left;
left = left.next;
} else {
newHead.next = right;
right = right.next;
}
// 每次迭代向后移动一位
newHead = newHead.next;
}
// 迭代结束是因为有一个链表到头了，那么将另一个接到后面
newHead.next = left === null ? right : left;
// 注意不要返回第一个节点
return res.next;
};相交链表
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。Leetcode 160
方法一：哈希集合
javascript
const getIntersectionNode = (headA, headB) => {
if (headA === null || headB === null) return null;
// 创建一个 Set 集合，也可以用 Map 实现
const visited = new Set();
// 遍历从 headA 开始的链表，将其放入集合
let temp = headA;
while (temp !== null) {
visited.add(temp);
temp = temp.next;
}
// 遍历从 headB 开始的链表
temp = headB;
while (temp !== null) {
if (visited.has(temp)) {
// 如果集合中有遍历到的节点，说明相交，并且此时迭代的是第一个相交的节点，直接返回节点
return temp;
}
temp = temp.next;
}
// 如果遍历完毕没有发现相交节点，返回 null
return null;
};const getIntersectionNode = (headA, headB) => {
if (headA === null || headB === null) return null;
// 创建一个 Set 集合，也可以用 Map 实现
const visited = new Set();
// 遍历从 headA 开始的链表，将其放入集合
let temp = headA;
while (temp !== null) {
visited.add(temp);
temp = temp.next;
}
// 遍历从 headB 开始的链表
temp = headB;
while (temp !== null) {
if (visited.has(temp)) {
// 如果集合中有遍历到的节点，说明相交，并且此时迭代的是第一个相交的节点，直接返回节点
return temp;
}
temp = temp.next;
}
// 如果遍历完毕没有发现相交节点，返回 null
return null;
};方法二：双指针
javascript
const getIntersectionNode = (headA, headB) => {
if (headA === null || headB === null) return null;
// 创建两个指针分别指向 headA，headB，开始迭代
let pA = headA,
pB = headB;
while (pA !== pB) {
// 如果某个指针指向了 null，说明当前链到尾部，则将指针指向另一个链头部
pA = pA === null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
}
// 1. 如果两个指针相等且不为 null，说明有相交，此时任意指针都是第一个相交的节点
// 2. 如果两个指针同时为 null，说明没有相交，返回指针指的 null
return pA;
};const getIntersectionNode = (headA, headB) => {
if (headA === null || headB === null) return null;
// 创建两个指针分别指向 headA，headB，开始迭代
let pA = headA,
pB = headB;
while (pA !== pB) {
// 如果某个指针指向了 null，说明当前链到尾部，则将指针指向另一个链头部
pA = pA === null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
}
// 1. 如果两个指针相等且不为 null，说明有相交，此时任意指针都是第一个相交的节点
// 2. 如果两个指针同时为 null，说明没有相交，返回指针指的 null
return pA;
};二叉树相关
前置知识
二叉树的深度优先遍历
javascript
const traversal = (tree) => {
const result = [];
const recursion = (node) => {
if (node) {
// 根据下面三行代码顺序不同，可以得到先序遍历、中序遍历、后序遍历，此时当前节点（根）先入栈，所以为先序遍历
result.push(node.value); // 当前节点入栈
dfs(node.left); // 左子节点
dfs(node.right); // 右子节点
}
};
recursion(tree);
return result;
};const traversal = (tree) => {
const result = [];
const recursion = (node) => {
if (node) {
// 根据下面三行代码顺序不同，可以得到先序遍历、中序遍历、后序遍历，此时当前节点（根）先入栈，所以为先序遍历
result.push(node.value); // 当前节点入栈
dfs(node.left); // 左子节点
dfs(node.right); // 右子节点
}
};
recursion(tree);
return result;
};二叉树的广度优先遍历
javascript
const traversal = (tree) => {
const result = []; // 结果栈
const order = [tree]; // 记录节点位置的栈（顺序栈）
const count = 0; // 用来记录顺序栈执行到的位置（顺序）
const recursion = () => {
// 入结果栈的节点必须从顺序栈按顺序取
let node = order[count];
if (node) {
// 当前节点入结果栈
result.push(node.value);
// 分别将左右子节点入顺序栈尾
if (node.left) order.push(node.left);
if (node.right) order.push(node.right);
// 当前顺序栈的节点处理完了，顺序+1
count++;
// 递归进行下个顺序节点的处理和子节点的记录
recursion();
}
};
recursion();
return result;
};const traversal = (tree) => {
const result = []; // 结果栈
const order = [tree]; // 记录节点位置的栈（顺序栈）
const count = 0; // 用来记录顺序栈执行到的位置（顺序）
const recursion = () => {
// 入结果栈的节点必须从顺序栈按顺序取
let node = order[count];
if (node) {
// 当前节点入结果栈
result.push(node.value);
// 分别将左右子节点入顺序栈尾
if (node.left) order.push(node.left);
if (node.right) order.push(node.right);
// 当前顺序栈的节点处理完了，顺序+1
count++;
// 递归进行下个顺序节点的处理和子节点的记录
recursion();
}
};
recursion();
return result;
};重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。Leetcode 剑指 offer 07
javascript
const buildTree = (preorder, inorder) => {
// 使用 map 存放中序遍历，key 为每个值的下标
let rootMap = new Map();
for (let i = 0; i < inorder.length; i++) {
rootMap.set(inorder[i], i);
}
//递归函数的三个参数分别对应：先序中根节点位置，中序中的左边界，中序中的右边界
const fn = (root, left, right) => {
// 左右边界会逐渐向中间靠拢，所以当左边界超出右边界，说明已经完成
if (left > right) return null;
// 从先序中获取当前根节点
let node = new TreeNode(preorder[root]);
// 拿到当前根节点在中序遍历中的位置
let site = rootMap.get(preorder[root]);
// 递归左子树
node.left = fn(root + 1, left, site - 1);
// 递归右子树，根节点位置：root + 左子树节点数量 + 1
node.right = fn(root + (site - left) + 1, site + 1, right);
// 返回拼接好的树节点
return node;
};
return fn(0, 0, inorder.length - 1);
};const buildTree = (preorder, inorder) => {
// 使用 map 存放中序遍历，key 为每个值的下标
let rootMap = new Map();
for (let i = 0; i < inorder.length; i++) {
rootMap.set(inorder[i], i);
}
//递归函数的三个参数分别对应：先序中根节点位置，中序中的左边界，中序中的右边界
const fn = (root, left, right) => {
// 左右边界会逐渐向中间靠拢，所以当左边界超出右边界，说明已经完成
if (left > right) return null;
// 从先序中获取当前根节点
let node = new TreeNode(preorder[root]);
// 拿到当前根节点在中序遍历中的位置
let site = rootMap.get(preorder[root]);
// 递归左子树
node.left = fn(root + 1, left, site - 1);
// 递归右子树，根节点位置：root + 左子树节点数量 + 1
node.right = fn(root + (site - left) + 1, site + 1, right);
// 返回拼接好的树节点
return node;
};
return fn(0, 0, inorder.length - 1);
};二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。Leetcode 236
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
javascript
// 需要从下到上，所以使用后序遍历（后序遍历是天然的回溯）
var lowestCommonAncestor = (root, p, q) => {
// 如果找到了节点 p 或者 q，或者遇到空节点，则返回当前节点
if (root === null || root === p || root === q) {
return root;
}
// 后序遍历先处理子节点
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
// 根据子节点的返回值处理当前节点
if (left !== null && right !== null) {
// 如果 left 和 right 都不为空，说明此时 root 就是最近公共节点
return root;
}
// 其他情况返回不为空的节点
if (left === null) {
return right;
}
return left;
};// 需要从下到上，所以使用后序遍历（后序遍历是天然的回溯）
var lowestCommonAncestor = (root, p, q) => {
// 如果找到了节点 p 或者 q，或者遇到空节点，则返回当前节点
if (root === null || root === p || root === q) {
return root;
}
// 后序遍历先处理子节点
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
// 根据子节点的返回值处理当前节点
if (left !== null && right !== null) {
// 如果 left 和 right 都不为空，说明此时 root 就是最近公共节点
return root;
}
// 其他情况返回不为空的节点
if (left === null) {
return right;
}
return left;
};二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null。Leetcode 700
javascript
/**
* 二叉搜索树满足的性质：左子树所有节点的元素值均小于根的元素值；右子树所有节点的元素值均大于根的元素值。
* 所以我们可以根据这个性质，进行定向递归
*/
const searchBST = (root, val) => {
if (!root) {
// 如果 root 没有值，说明递归已到底层
return null;
}
if (val === root.val) {
// 如果找到，直接返回节点
return root;
}
// 递归时根据当前节点的值和目标值的比较，决定往什么方向查找
return searchBST(val < root.val ? root.left : root.right, val);
};/**
* 二叉搜索树满足的性质：左子树所有节点的元素值均小于根的元素值；右子树所有节点的元素值均大于根的元素值。
* 所以我们可以根据这个性质，进行定向递归
*/
const searchBST = (root, val) => {
if (!root) {
// 如果 root 没有值，说明递归已到底层
return null;
}
if (val === root.val) {
// 如果找到，直接返回节点
return root;
}
// 递归时根据当前节点的值和目标值的比较，决定往什么方向查找
return searchBST(val < root.val ? root.left : root.right, val);
};删除二叉搜索树中的节点
给定一个二叉搜索树（BST）的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。Leetcode 450
javascript
/**
* 题目提到删除时还要保证 BST 的性质，所以在删除时会遇到以下情况：
* 1. 要删除的节点恰好是末端节点，两个子节点都为空，那么它可以直接删掉
* 2. 要删除的节点只有一个非空子节点，那么只要让它非空子孩子接替自己的位置即可
* 3. 要删除的节点有两个子节点，为了不破坏 BST 的性质，我们需要找右子树中最小的节点来顶替它，然后再删除这个最小的节点
*/
var deleteNode = function (root, key) {
// 非空判断
if (!root) return root;
// 用于获取比输入节点大的最小节点
let getMin = (node) => {
// BST 中最左边的就是最小的
while (node.left) {
node = node.left;
}
return node;
};
if (root.val == key) {
// 如果当前节点的值等于要删除的值
// 这两个 if 把情况 1 和 2 都处理了
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 处理情况 3
let minNode = getMin(root.right);
root.val = minNode.val;
// 找到最小的顶替它之后还要删除这个最小的节点
root.right = deleteNode(root.right, minNode.val);
} else if (root.val < key) {
// 如果当前值比要删除的值小，向右查找，返回时在当前节点右子节点
root.right = deleteNode(root.right, key);
} else {
// 如果当前值比要删除的值大，向左查找，返回时在当前节点左子节点
root.left = deleteNode(root.left, key);
}
// 返回处理后的当前节点（最后为树的根节点）
return root;
};/**
* 题目提到删除时还要保证 BST 的性质，所以在删除时会遇到以下情况：
* 1. 要删除的节点恰好是末端节点，两个子节点都为空，那么它可以直接删掉
* 2. 要删除的节点只有一个非空子节点，那么只要让它非空子孩子接替自己的位置即可
* 3. 要删除的节点有两个子节点，为了不破坏 BST 的性质，我们需要找右子树中最小的节点来顶替它，然后再删除这个最小的节点
*/
var deleteNode = function (root, key) {
// 非空判断
if (!root) return root;
// 用于获取比输入节点大的最小节点
let getMin = (node) => {
// BST 中最左边的就是最小的
while (node.left) {
node = node.left;
}
return node;
};
if (root.val == key) {
// 如果当前节点的值等于要删除的值
// 这两个 if 把情况 1 和 2 都处理了
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 处理情况 3
let minNode = getMin(root.right);
root.val = minNode.val;
// 找到最小的顶替它之后还要删除这个最小的节点
root.right = deleteNode(root.right, minNode.val);
} else if (root.val < key) {
// 如果当前值比要删除的值小，向右查找，返回时在当前节点右子节点
root.right = deleteNode(root.right, key);
} else {
// 如果当前值比要删除的值大，向左查找，返回时在当前节点左子节点
root.left = deleteNode(root.left, key);
}
// 返回处理后的当前节点（最后为树的根节点）
return root;
};完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root，求出该树的节点个数。完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。Leetcode 222
javascript
const countNodes = (root) => {
// 记录左、右子树的高度
let hl = 0,
hr = 0;
// 左右子树指针
let headL = root,
headR = root;
// 计算左子树高
while (headL) {
headL = headL.left;
hl++;
}
// 计算右子树高
while (headR) {
headR = headR.right;
hr++;
}
// 如果左右子树的高度相同，则是一棵满二叉树
if (hl == hr) {
// 满二叉树的节点数公式：2^h - 1
return Math.pow(2, hl) - 1;
}
// 如果左右高度不同，则按照普通二叉树的逻辑计算，两个递归只有一个会真的递归下去，另一个一定会触发hl == hr而立即返回，不会递归下去
return 1 + countNodes(root.left) + countNodes(root.right);
};const countNodes = (root) => {
// 记录左、右子树的高度
let hl = 0,
hr = 0;
// 左右子树指针
let headL = root,
headR = root;
// 计算左子树高
while (headL) {
headL = headL.left;
hl++;
}
// 计算右子树高
while (headR) {
headR = headR.right;
hr++;
}
// 如果左右子树的高度相同，则是一棵满二叉树
if (hl == hr) {
// 满二叉树的节点数公式：2^h - 1
return Math.pow(2, hl) - 1;
}
// 如果左右高度不同，则按照普通二叉树的逻辑计算，两个递归只有一个会真的递归下去，另一个一定会触发hl == hr而立即返回，不会递归下去
return 1 + countNodes(root.left) + countNodes(root.right);
};数组相关
用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points，返回引爆所有气球所必须射出的最小弓箭数。Leetcode 452
javascript
const findMinArrowShots = (points) => {
if (!points.length) {
return 0;
}
// 先对气球按右边界进行排序
points.sort((a, b) => a[1] - b[1]);
// 创建一个指针记录第一个气球的右边界
let pos = points[0][1];
// 记录弓箭数
let ans = 1;
// 对排序好的气球进行迭代
for (let balloon of points) {
// 如果迭代的气球的左边界大于记录的右边界，则两个气球无相交，只能多用一支箭
if (balloon[0] > pos) {
// 指针记录无相交气球的右边界
pos = balloon[1];
// 弓箭数加 1
ans++;
}
}
return ans;
};const findMinArrowShots = (points) => {
if (!points.length) {
return 0;
}
// 先对气球按右边界进行排序
points.sort((a, b) => a[1] - b[1]);
// 创建一个指针记录第一个气球的右边界
let pos = points[0][1];
// 记录弓箭数
let ans = 1;
// 对排序好的气球进行迭代
for (let balloon of points) {
// 如果迭代的气球的左边界大于记录的右边界，则两个气球无相交，只能多用一支箭
if (balloon[0] > pos) {
// 指针记录无相交气球的右边界
pos = balloon[1];
// 弓箭数加 1
ans++;
}
}
return ans;
};全排列
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。Leetcode 46
javascript
/**
* 选数进行组合的过程可以看做二叉树，
* 树的每条完整路径是选择的结果（递归到最底层后进行当前路径记录），
* 同层的树节点是将要选择的选项（迭代所有数字，跳过已经使用的数字）
*/
const permute = (nums) => {
// 结果数组
const res = [];
// 用于记录数字的使用
const used = {};
function dfs(path) {
// 个数选够了
if (path.length == nums.length) {
// 拷贝一份path，加入解集res，结束递归分支后会回溯，所以必须是拷贝
res.push(path.slice());
// 结束当前递归分支
return;
}
// for枚举出每个可选的选项
for (const num of nums) {
if (used[num]) continue; // 使用过的，跳过
path.push(num); // 选择当前的数，加入 path
used[num] = true; // 加入 path 后需记录一下使用
dfs(path); // 基于选了当前的数，递归
path.pop(); // 递归结束后进行回溯，将最后选的数pop出来
used[num] = false; // 撤销这个记录
}
}
dfs([]); // 递归的入口，空 path 传进去
return res;
};/**
* 选数进行组合的过程可以看做二叉树，
* 树的每条完整路径是选择的结果（递归到最底层后进行当前路径记录），
* 同层的树节点是将要选择的选项（迭代所有数字，跳过已经使用的数字）
*/
const permute = (nums) => {
// 结果数组
const res = [];
// 用于记录数字的使用
const used = {};
function dfs(path) {
// 个数选够了
if (path.length == nums.length) {
// 拷贝一份path，加入解集res，结束递归分支后会回溯，所以必须是拷贝
res.push(path.slice());
// 结束当前递归分支
return;
}
// for枚举出每个可选的选项
for (const num of nums) {
if (used[num]) continue; // 使用过的，跳过
path.push(num); // 选择当前的数，加入 path
used[num] = true; // 加入 path 后需记录一下使用
dfs(path); // 基于选了当前的数，递归
path.pop(); // 递归结束后进行回溯，将最后选的数pop出来
used[num] = false; // 撤销这个记录
}
}
dfs([]); // 递归的入口，空 path 传进去
return res;
};最长递增子序列
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。Leetcode 300
javascript
const lengthOfLIS = (nums) => {
// 初始化一个子序列数组
const dp = new Array(nums.length).fill(1);
// 遍历数组，找出以当前遍历位置的元素结尾的子序列，在 dp 中更新他们的长度
for (let i = 0; i < nums.length; i++) {
// i 与 i 前面的元素比较
for (let j = 0; j < i; j++) {
// 找比 i 小的元素，找到一个，就让当前序列的最长子序列长度加 1
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// 找出最大的子序列
return Math.max(...dp);
};const lengthOfLIS = (nums) => {
// 初始化一个子序列数组
const dp = new Array(nums.length).fill(1);
// 遍历数组，找出以当前遍历位置的元素结尾的子序列，在 dp 中更新他们的长度
for (let i = 0; i < nums.length; i++) {
// i 与 i 前面的元素比较
for (let j = 0; j < i; j++) {
// 找比 i 小的元素，找到一个，就让当前序列的最长子序列长度加 1
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// 找出最大的子序列
return Math.max(...dp);
};
