算法笔记

数组

704.二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1 

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while(left <= right){
        let mid = Math.floor((right + left) / 2);
        if(target < nums[mid]) right = mid - 1;
        else if(target > nums[mid]) left = mid + 1;
        else return mid;
    }
    return -1;
};

977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

暴力解法

循环每个数组，将其平方，随后使用sort函数进行排序。

var sortedSquares = function(nums) {
    for(let i = 0;i < nums.length;i++){
        nums[i] = Math.pow(nums[i],2);
    }
    nums.sort((a,b) => a-b);
    return nums;
};

双指针

因为给的数组是升序的，所以可以定义两个指针——left和right，分别指向队头和队尾，然后判断两个值的大小，进行交换。

var sortedSquares = function(nums) {
    let result = []; // 新数组
    let len = nums.length - 1; // 新数组赋值从队尾开始，因为数组升序，最大的要么是负数的平方，要么是正数的平方
    let l = 0, r = nums.length - 1; // l指向对头,r指向队尾
    while(l <= r){
        if(nums[l] * nums[l] < nums[r] * nums[r]){ // 当l的平方小于r的平方，将结果数组的队尾赋值为r的平方
            result[len--] = nums[r]*nums[r];
            r--; // r向前移动一位
        }else{ // 相反，当r的平方小于l的平方，将结果数组的队尾赋值为l的平方
            result[len--] = nums[l]*nums[l];
            l++; // l向后移动一位
        }
    }
    return result;
};

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

滑动窗口

采用滑动窗口，定义两个指针i和j，将窗口长度赋初值为Infinity，不断的调节子序列的起始位置和终止位置

• 当窗口中的和小于target时，j++
• 当窗口中的和大于等于target时，判断窗口的长度与之前相比是大还是小，小就赋值，大就跳过
• i++，sum减去滑动窗口起始值

var minSubArrayLen = function(target, nums) {
    let result = Infinity; // 结果值，赋值为极大值
    let sum = 0; // 滑动窗口中所有值的和
    let start = 0; // 滑动窗口起始指针
    let len = 0; // 滑动窗口长度
    for(let end = 0;end < nums.length;end++){
        sum += nums[end]; // 当sum小于target时，继续循环
        while(sum >= target){ // 大于target时，进入循环
            len = end - start + 1;  // 获取滑动窗口的长度
            result = result > len ? len : result; // 如果大于之前的值，则忽视，如果小，则将其赋给result
            sum -= nums[start++]; // 滑动窗口向后滑动
        }
    }    
    return result === Infinity ? 0 : result;
};

59.螺旋矩阵

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

做法

• 生成一个 n×n 空矩阵 res，随后模拟整个向内环绕的填入过程：

  • 定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 tar = n * n；
  • 当 num <= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：
    • 执行 num += 1：得到下一个需要填入的数字；
    • 更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。
  • 使用num <= tar而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。

• 最终返回res 即可。

var generateMatrix = function(n) {
    let top = 0, right = n - 1, bottom = n - 1, left = 0; // 定义边界
    let num = 1,target = n*n; // 设置初值和结束值
    const res = new Array(n).fill(0).map(() => new Array(n).fill(0)); // 创建一个N*N的二维数组
    while(num <= target){ // 当num小于target时，进入循环
        for(let i = left;i <= right;i++){ // 从左往右，循环后一层top已填满
            res[top][i] = num++; // 
        }
        top++; // top加1
        for(let i = top;i <= bottom;i++){ // 从上往下，循环后一列right已填满
            res[i][right] = num++;
        }
        right--;// right加1
        for(let i = right;i >= left;i--){ // 从右往左，循环后一层bottom已填满
            res[bottom][i] = num++;
        }
        bottom--;// bottom减1
        for(let i = bottom;i >= top;i--){ // 从下往上，循环后一列left已填满
            res[i][left] = num++;
        }
        left++;// left加1
    }
    return res;
};

链表

203.移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

虚拟头节点

创建虚拟头节点，创建两个指针，第一个h指向虚拟头节点，第二个fast指向head节点，随后以fast不为null作为循环条件，

• 当fast.val与给定值相等时，将h指向fast的下一个节点
• 不相等，将h和fast都指向下一个节点

var removeElements = function(head, val) {
    let ret = new ListNode(0, head);
    let h = ret;
    let fast = h.next;
    while(fast){
        if(fast.val === val){
            h.next = fast.next;
            fast = fast.next;
        }else{
            fast = fast.next;
            h = h.next; 
        }
    }
    return ret.next;
};

或者只用一个节点。

• cur指向虚拟头节点，循环条件为cur.next不为null
• 当cur.next的值等于val时，将其next指针指向cur.next.next，然后用continue跳出循环
• 如果不等于，cur指向下一个节点

var removeElements = function(head, val) {
    let ret = new ListNode(0, head);
    let cur = ret;
    while(cur.next){
        if(cur.next.val === val){
            cur.next = cur.next.next;
            continue;
        }
        cur = cur.next;
    }
    return ret.next;
};

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

双指针

让一个指针slow指向头节点，另一个fast指向头节点的下一个节点，然后进入循环，条件是fast不为null。

• 定义一个中间变量保存fast.next，不保存的话当进行反转时，fast.next就无法获取到了
• 随后进行反转

var reverseList = function(head) {
    if(head === null) return head; // 容错，当head为null，直接返回head
    let slow = head,fast = head.next;
    slow.next = null;
    while(fast !== null){
        let next = fast.next; // 定义一个中间变量保存fast.next
        fast.next = slow; // 快指针指向慢指针
        slow = fast; // 慢指针赋值为快指针
        fast = next; // 快指针等于保存的fast.next
    }
    return slow;
};

栈

将所有节点存储栈中，随后创建一个虚拟头节点，不断从栈顶取出元素，将头节点.next指向取出的元素。

var reverseList = function(head) {
    if(head === null) return head;
    let stack = [];
    let h = head;
    while(h){
        stack.push(h);
        h = h.next;
    }
    let list = new ListNode(0); // 定义新的链表
    h = list; // h指向新链表
    while(stack.length){
        let node = stack.pop(); // 不断从栈顶取出元素
        h.next = node; // h.next指向取出来的元素 
        h = h.next; // h 赋值为hnext
    }
    h.next = null;
    return list.next;
};

24.两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

虚拟头节点

var swapPairs = function(head) {
    let ret = new ListNode(0, head), temp = ret;// 创建新的虚拟节点
    while(temp.next && temp.next.next){ // 循环条件为temp的next和next.next不为空
        let pre = temp.next,cur = temp.next.next; // 暂存两个需要交换的节点
        temp.next = cur; // 进行交换
        pre.next = cur.next;
        cur.next = pre;
        temp = pre; // 此时pre交换为链表的第二个节点，将temp赋值为pre，用于进入下个循环
    }
    return ret.next;
};

19.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

• 定义fast指针和slow指针，初始值为虚拟头结点，如图：

• fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
• fast和slow同时移动，直到fast指向末尾，如题：
• 删除slow指向的下一个节点，如图：

var removeNthFromEnd = function(head, n) {
    let ret = new ListNode(0, head);
    let fast = ret, slow = ret;
    while(n--) fast = fast.next;
    while(fast.next){
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return ret.next;
};

160.链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

map

将链表headA的所有节点存在map中，循环链表headB，与map做判断，找得到则直接返回，找不到返回null。

var getIntersectionNode = function(headA, headB) {
    const map = new Map();
    while(headA !== null){
        map.set(headA, 1);
        headA = headA.next;
    }
    while(headB !== null){
        if(map.get(headB))  return headB;
        headB = headB.next;
    }
    return null;
};

142.环形链表II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

map

将所有节点存入map，key为节点，value为出现的次数。

• 如果获取到的节点的value为1，则说明是循环链表的入口，直接返回
• 否则继续循环
• 如果出了循环，说明不是循环链表，返回null

var detectCycle = function(head) {
    let p = head;
    let hashmap = new Map();
    while(p !== null){
        if(hashmap.get(p) === 1) return p;
        else {
            hashmap.set(p, 1);
        }
        p = p.next;
    }
    return null;
};

快慢指针

var detectCycle = function(head) {
    if(!head || !head.next) return null;
    let slow = head.next, fast = head.next.next;
    while(fast && fast.next && fast !== slow){
        fast = fast.next.next;
        slow = slow.next;
    }
    if(!fast || !fast.next) return null;
    slow = head;
    while(slow !== fast){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};

2.两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

循环逐个相加

var addTwoNumbers = function(l1, l2) {
    let addOne = 0; // 进位
    let sum = new ListNode(0); // 虚拟头节点
    let head = sum; // 保存头节点，便于返回
    while(addOne || l1 || l2){
        // l1、l2长度不定，所以可能一个已经为空了，另一个还存在，所以需要判断是否为空，为空则赋0，不为空则是它的val
        let val1 = l1 ? l1.val : 0; 
        let val2 = l2 ? l2.val : 0;
        // 单个位相加，要加上进位
        let r1 = val1 + val2 + addOne;
        // 判断相加后的结果是不是大于0，大于0则进位赋值为1，否则为0
        addOne = r1 >= 10 ? 1 : 0;
        // 定义新节点，连接虚拟头节点的next
        sum.next = new ListNode(r1 % 10 );
        sum = sum.next;
        // 如果l1或l2有next节点，则将其赋为它的next节点
        if(l1) l1 = l1.next;
        if(l2) l2 = l2.next;
    }
    return head.next;
};

双指针法

27.移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

做法

暴力

双层循环，外循环判断当前值是否等于val，内循环将数组从当前值开始，不断将后面的值往前挪一格。

var removeElement = function(nums, val) {
    let len = nums.length;
    for(let i = 0;i < len;i++){
        if(nums[i] === val){ // 当循环到等于val的值时，再进行一次循环，将i以后的元素都往前移一位
            for(let j = i + 1;j < nums.length;j++){
                nums[j-1] = nums[j]; 
            }
            i--; // 因为i以后的数值都往前移了一位，所以i也向前移动一位
            len--;
        }
        
    }
    return len;
};

快慢指针

定义一个fast和slow指针，for循环遍历，当前值不等于val时，快慢指针同时递增，而相等时，快指针继续递增，慢指针停止递增,当不相等时，当前慢指针所对应的val值就会被快指针对应的值覆盖。

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

var removeElement = function(nums, val) {
   let slow = 0; // 慢指针，用于指向新数组的下标
   for(let fast = 0;fast < nums.length;fast++){ // 快指针，用于寻找新数组的元素
    if(nums[fast] !== val){ // 当快指针对应的值不等于val时,将慢指针对应的值赋值为快指针对应的值
        nums[slow] = nums[fast];
        slow++;
    }
   }
   return slow;
};

151.反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

做法

双指针

1. 如何移除字符串中多余的空格
   双指针法：这里的处理就跟以前有一道数组题移除元素的方法是类似的，首先我们定义两个指针，初始都指向数组的0下标,快指针每一次向前移动的时候判断当前元素是否是一个空格，如果不是那么就把当前元素赋值给慢指针所指向的位置，然后快慢指针同时往前移动一步，这里需要注意一下，因为两个不同的单词之间需要一个空格，所以我们必须需要判断slow指针是否指向字符串数组第一个下标(因为第一个单词前面不需要空格)，然后接下来每一次都让slow指向的位置都赋值为空格，这样两个不同的单词之间就会产生一个空格了

2. 如何将处理后的字符串整体翻转
   双指针法：只需要定义两个指针，分别指向数组的头部和尾部的位置，然后一起往中间靠拢，相互调换位置即可

3. 如何对单个单词进行翻转
   双指针法：(如：”drlow ollhe”),我们可以轻易发现字符串中的空格跟最后一个单词的最后一个字符的位置就是每一次置换位置的判断条件；所以通过第二部的函数合理控制好边界就可以完成每一个单词的翻转

var reverseWords = function(s) {
    function removeExtraSpaces(s){
        let slow = 0,fast = 0;
        for(;fast < s.length;fast++){
            if(s[fast] !== ' '){
                if(slow !== 0){
                    s[slow++] = ' ';
                }
                while(fast < s.length && s[fast] !== ' '){
                    s[slow] = s[fast];
                    fast++;
                    slow++;
                }
            }
        }
        s.length = slow;
    }
    function reverseWords(s, start, end){
        let slow = start, fast = end;
        while(slow < fast){
            let temp = s[slow];
            s[slow] = s[fast];
            s[fast] = temp;
            slow ++;
            fast --;
        }
    }
    let arr = Array.from(s);
    removeExtraSpaces(arr);
    reverseWords(arr, 0 ,arr.length - 1);
    let begin = 0;
    for(let i = 0;i <= arr.length;i++){
        if(arr[i] === ' ' || i === arr.length){
            reverseWords(arr, begin, i - 1);
            begin = i + 1;
        }
    }
    return arr.join("");
};

哈希表

49.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

排序

遍历数组，将每一个元素转换成字符数组，进行排序，将排序后的字符作为哈希表的key，如果是异位词，那么排序后的字符数组也是相同的。

var groupAnagrams = function(strs) {
    let map = new Map();
    for(let s of strs){
        let sArr = s.split("");// 将字符串转换为字符数组
        sArr.sort();// 排序
        let key = sArr.toString(); // 获取排序后的字符串形式
        let list = map.get(key) ? map.get(key) : new Array();// 如果map有了list就用原来的，没有就新创建一个
        list.push(s);// 将字符推入list
        map.set(key, list);
    }
    return Array.from(map.values())
};

栈和队列

232.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

• 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

var MyQueue = function() {
    this.que1 = [];
    this.que2 = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.que1.push(x); 
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    for(let i = this.que1.length-1;i>=0;i++){
        this.que2.push(this.que1[i]);
    }
    this.que1.length = 0;
    const num = this.que2.pop();
    return num;
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    const  num = (this.que1.length === 0) ? this.que1[this.que1.length-1] : this.que1[0];
    return num;
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return (this.que1.length === 0 && this.que2.length === 0);
};

225.用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

代码

var MyStack = function() {
    this.que1 = [];
    this.que2 = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.que1.push(x);
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    
    return this.que1.pop();
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    return this.que1[this.que1.length - 1]
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return !this.que1.length && !this.que2.length;
};

20.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

var isValid = function(s) {
    let stack = [];
    s = s.split("");
    let right = [')','}',']'];
 
    for(let i = 0;i < s.length;i++){
        if(!right.includes(s[i])){
            stack.push(s[i]);
        }else{
            switch(s[i]){
                case ")":
                    if(stack.pop()!='(')
                        return false;
                    break;
                case "}":
                    if(stack.pop()!='{')
                        return false;
                    break;
                case "]":
                    if(stack.pop()!='[')
                        return false;
                    break;
            }
        }

    }
    if(stack.length==0){
        return true;
    }else{
        return false;
    }
};

1047.删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. 1 <= S.length <= 20000
2. S 仅由小写英文字母组成。

代码

var removeDuplicates = function(s) {
    let stack = [];
    stack.push(s[0])
    for(let i = 1;i < s.length;i++){
        let x = stack.pop();
        x === s[i] ? true : stack.push(x,s[i]); 
    }
    return stack.join("");
};

150.逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

• 1 <= tokens.length <= 104
• tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

思路

遇到数字入栈，遇到运算符号取出栈顶前两个元素，进行对应的运算，再将运算结果推入栈中，进行下一次运算。

var evalRPN = function(tokens) {
    const op = ['+','-','*','/'];
    let stack = [];
    for(let i of tokens){
        console.log(i);
        if(!op.includes(i)){
            stack.push(Number(i));
        }else{
            let num1 = stack.pop();
            let num2 = stack.pop();
            let res;
            switch(i){
                case '+':
                    res = num1+num2;
                    break;
                case '-':
                    res = num2-num1;
                    break;
                case '*':
                    res = num1*num2;
                    break;
                case '/':
                    res = num2/num1 | 0;
                    break;
            }
            stack.push(res);
        }
    }
    return stack[0];

};

347.前K个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: []

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

思路

用map记录每一个数和对应出现的次数，然后将其转换为数组根据value进行降序排序，将前k个值推入结果数组。

var topKFrequent = function(nums, k) {
    let map = new Map();
    let result = [];
    for(let i of nums){//用map记录每一个数和对应出现的次数
        if(map.get(i)){
            map.set(i, map.get(i) + 1);
        }else {
            map.set(i, 1);
        }
    }
    let mapArr = Array.from(map);//降序排序
    mapArr.sort((a, b) => b[1] - a[1]);
    for(let i = 0;i < k;i++){
        result.push(mapArr[i][0]);//将前k个值推入结果数组
    }
    return result;
};

二叉树

144.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

迭代

var preorderTraversal = function(root) {
    let result = [];
    let stack = []; // 定义栈
    if(!root) return result; // 容错，如果root为空直接返回空数组
    stack.push(root); 
    while(stack.length > 0){
        let node = stack.pop();
        result.push(node.val);
        node.right && stack.push(node.right); // 先推入右节点再推入左节点因为栈先进后出，为了先输出左节点
        node.left && stack.push(node.left);
    }
    return result;
};

94.二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

迭代

var inorderTraversal = function(root) {
    let result = [];
    if(!root) return result; // 容错，如果root为空直接返回空数组
    let cur = root; // 定义一个指针节点
    let stack = [];
    while(cur !== null || stack.length > 0){
        while(cur){ // 因为中序遍历是要先遍历左节点，所以将所有左节点推入栈
            stack.push(cur);
            cur = cur.left;
        }
        let node = stack.pop(); // 从栈中取出栈顶元素，也就是最底最左的节点
        result.push(node.val); // 将其推入结果数组
        cur = node.right; // cur赋值为node的右节点，继续进入循环
    }
    return result;
};

145.二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点的数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

迭代

先将二叉树进行中右左遍历，再将结果反转就是左右中后续遍历。

var postorderTraversal = function(root) {
    let result = [];
    if(!root) return result;
    let stack = [];
    stack.push(root);
    while(stack.length){
        let node = stack.pop();
        result.push(node.val);
       	// 改变节点推入顺序，先推入左节点，将遍历顺序变为中右左
        node.left && stack.push(node.left);
        node.right && stack.push(node.right);
    }
    // 将结果反转
    return result.reverse();
}

102.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

迭代

采用队列，将根节点推入队列，每次计算当前层的长度len，循环len次，从队列中取出当前层的节点，将值推入结果数组，同时判断当前节点有没有孩子节点，有的话将孩子节点推入队列。

var levelOrder = function(root) {
    let queue = [];
    let res = [];
    if(!root) return queue;
    queue.push(root);// 将根节点推入队列
    while(queue.length){// 循环条件为队列不为空
        let len = queue.length;// 获取队列长度（即当前层的长度）
        let curLevel = [];// 当前节点存放的数组
        for(let i = 0;i < len;i++){// 将当前层所有节点取出
            let cur = queue.shift();// 采用shift，队列先进先出
            curLevel.push(cur.val);// 将节点的val推入数组
            // 当且仅当当前节点有孩子节点才将其孩子节点推入数组
            cur.left && queue.push(cur.left);
            cur.right && queue.push(cur.right);
        }
        res.push(curLevel);// 将当前层的节点值推入最后的结果数组
    }
    return res;
};

226.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

递归

采用先序遍历，先判断当前二叉树是否是null，是的话就返回null，遍历交换当前节点的左右节点，然后再递归，将左右节点分别传入函数，最后返回root二叉树。

function invertTree(root: TreeNode | null): TreeNode | null {
    if(!root) return null;
    let left  = root.left;//用变量获取左右节点
    let right = root.right;
    root.left = right;//交换左右节点
    root.right = left;
    invertTree(root.left);//将左右节点传入函数进行递归交换
    invertTree(root.right);
    return root;
};

迭代

采用栈存储当前节点，循环条件是栈的长度不为0。然后定义变量存储出栈的值，判断变量是否为null，是的话跳过本次循环，不是则交换左右节点。将左右节点再推入栈中,直到栈为空。

function invertTree(root: TreeNode | null): TreeNode | null {
    let stack = [];
    stack.push(root);//将根节点存储栈中
    while(stack.length>0){
        let t = stack.pop();//出栈
        if(t == null) continue;//如果t为空，则跳过本次循环，不交换
        let left = t.left;//分别用变量存储左右节点
        let right = t.right;
        t.left = right;//将t的左右节点进行交换
        t.right = left;
        stack.push(t.left);//将交换后的左右节点再推入栈中，进入循环
        stack.push(t.right);
    }
    return root;
};

101.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

子树堆成条件：

1. 它们两个根节点具有相同的值
2. 每个树的右子树都与另一个树的左子树镜像对称

递归

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

通过递归判断，第一次将树的根传两次进去，然后第二次传根的left和right进行判断，第三次传根left的left和根right的right以及根left的right和根right的left进行比较….以此类推，直到到树的底层为止

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}
//递归判断二叉树是否对称
const check = (p:TreeNode|null,q:TreeNode|null):boolean=>{
    if(!p && !q) return true;//判断两个节点是否同时不存在，不存在返回true
    if(!p || !q) return false;//如果只有一个不存在，说明不对称，返回false
    return p.val === q.val && check(p.left,q.right) && check(p.right,q.left); //第一个条件是两个节点的值是否相等，第二个条件是将左节点的左儿子和右节点的右儿子进行比较，第三个条件是将左节点的右儿子和右节点的左儿子进行比较
}
function isSymmetric(root: TreeNode | null): boolean {
    return check(root,root);//首次传两个根节点
};


//好理解的方法
var isSymmetric = function(root) {
    if(!root) return true;
    const isSymmetry = (left, right) =>{
        if(!left && !right) return true;
        else if(!left && right) return false;
        else if(left && !right) return false;
        else if(left.val !== right.val) return false;
        let isLeftTrue = isSymmetry(left.left,right.right);
        let isRightTrue = isSymmetry(left.right, right.left);
        return isLeftTrue && isRightTrue;
    }
    return isSymmetry(root.left, root.right);
};

迭代

使用队列，创建一个队列，先推入两次根节点，随后进行循环（循环条件是队列的长度），两次取出队列的值进行判断，如果两个节点都为空说明这两个节点是对称的，设置为continue，如果两个节点有一个为空或者它们的val值不相等，则返回false。然后分别推入节点的左儿子和另一个节点的右儿子，以及节点的右儿子和另一个节点的左儿子，再次进入循环。循环结束，返回true。

const check = (u:TreeNode|null , v:TreeNode|null):boolean=>{
    const q:TreeNode[] = [];//创建队列
    q.push(u);//推入根节点两次，因为要分别判断根的left和right
    q.push(v);
    while(q.length){//进行循环
        u = q.shift();//取出队列的前两个值进行判断
        v = q.shift();

        if(!u && !v) continue;//如果它们都为空说明是对称的，结束本次循环进入下次循环
        if((!u || !v) || u.val != v.val) return false;//如果它们有一个为空，或者值不相等，返回false
		//推入u的left和v的right，u的right和v的left，因为它们镜像，要比对的是它们的值
        q.push(u.left);
        q.push(v.right);

        q.push(u.right);
        q.push(v.left);
    }
    return true;//循环结束，说明是对称的
}
function isSymmetric(root: TreeNode | null): boolean {
    return check(root,root);
};

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

递归

如果我们知道了左子树和右子树的最大深度 l和 r，那么该二叉树的最大深度即为max⁡(l,r)+1
而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时返回0退出。

104. 二叉树的最大深度 - 力扣（Leetcode）

var maxDepth = function(root) {
    const deep = (root) => {
        if(!root) return 0;
        const left = deep(root.left) + 1;
        const right = deep(root.right) + 1;
        return left > right ? left : right;
    }
    return deep(root);
};

迭代

二叉树的最大深度就是它对应的层数，可以使用层序遍历来实现。

var maxDepth = function(root) {
    const queue = []
    if(!root) return 0;
    queue.push(root);
    let index = 0;// 表示层数的值
    while(queue.length){
        index++;// 每次遍历当层index++
        let len = queue.length;
        for(let i = 0;i < len;i++){
            let cur = queue.shift();
            cur.left && queue.push(cur.left);
            cur.right && queue.push(cur.right);
        }
    }
    return index;
};

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 [0, 105] 内
• -1000 <= Node.val <= 1000

思路

就是找到第一叶子节点所在的层次。

递归

大致上与最大深度一样，只不过存在特殊可能，当二叉树根节点的左子树或右子树为空时，照着最大深度做会把根节点所在的层当最最小深度返回，显然是不对的，所以在最后需要进行判断。

var minDepth = function(root) {
    const minDepth = (root) => {
        if(!root) return 0;
        let left = minDepth(root.left) + 1;// 获取左节点的深度
        let right = minDepth(root.right) + 1;// 获取右节点的深度
        if(root.left === null && root.right !== null){
            return right ; // 这是为了判断当根节点的左子树为空时，直接返回右子树的深度
        }
        if(root.right === null && root.left !== null){
            return left;// 这是为了判断当根节点的右子树为空时，直接返回左子树的深度
        }
        return Math.min(left,right); // 当根节点左右子树不为空时，这是可以返回left和right的最小值
    }
    return minDepth(root);
};

迭代

与最大深度的迭代方法差不多，使用层序遍历，只是最后循环当前层的时候最后一个条件为如果当前节点的左右节点都为空时，直接返回计算的index

var minDepth = function(root) {
    if(!root) return 0;
    const queue = [];
    queue.push(root);
    let index = 0;
    while(queue.length){
        index++;
        let len = queue.length;
        for(let i = 0;i < len;i++){
            let cur = queue.shift();
            if(cur.left) queue.push(cur.left);
            if(cur.right) queue.push(cur.right);
            if(!cur.left && !cur.right) return index;// 如果左右孩子为空，说明是叶子节点，即到最小深度
        }
    }
};

110.平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

递归

二叉树的高度指当前节点到叶子节点的边条数，力扣中指当前节点到叶子节点的节点个数

采用后序遍历，如果当前节点的左右节点的高度差的绝对值大于1，返回-1，小于等一1则返回它的当前节点的高度。

var isBalanced = function(root) {
    if(!root) return true;
    const Balance = (root) => {
        if(!root) return 0;// 递归中值条件
        let left = Balance(root.left);// 计算左子树的高度
        if(left === -1) return -1;// 如果左子树不为平衡二叉树返回-1
        let right = Balance(root.right);// 计算右子树的高度
        if(right === -1) return -1;// 如果右子树不为平衡二叉树返回-1
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right); // 判断 如果左子树的高度减去右子树的高度的绝对值大于1，返回-1，否则返回当前节点的高度
    }
    return !(Balance(root) === -1);
};

257.二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示：

• 树中节点的数目在范围 [1, 100] 内
• -100 <= Node.val <= 100

递归

var binaryTreePaths = function(root) {
    let str ="";// 路径字符串
    let result = [];// 结果数组
    // 递归参数为节点和表示路径的str字符串
    const path = (root, str) => {
        // 递归结束条件为当前节点是叶子节点
        if(root.left === null && root.right === null) {
            // 结果数组推入字符串加上当前节点的值的字符串
            result.push(str+root.val);
            return;
        }
        str +=root.val+'->';// 单层循环中str加上当前值和->箭头
        if(root.left){ // 如果当前节点左孩子不为空，则进入递归
            path(root.left, str);
        }
        if(root.right){// 如果当前节点右孩子不为空，则进入递归
            path(root.right, str);
        }
    }
    path(root, str);
    return result;
};

404.左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

提示:

• 节点数在 [1, 1000] 范围内
• -1000 <= Node.val <= 1000

递归

递归结束条件根据父节点判断左孩子节点是否为叶子节点。

即if(root.left && !root.left.left && !root.left.right)。

var sumOfLeftLeaves = function(root) {
    let num = 0;
    if(!root) return num;
    const leftLeave = (root) => {
        if(!root) return 0;
        if(!root.left && !root.right) return 0;// 叶子节点
        let leftValue = leftLeave(root.left);
        if(root.left && !root.left.left && !root.left.right){
            leftValue += root.left.val;
        }
        let rightValue = leftLeave(root.right);
        return leftValue + rightValue;
    }
    return leftLeave(root);
};

迭代

层次遍历每个节点，用递归的判断条件即可。

var sumOfLeftLeaves = function(root) {
    let num = 0;
    if(!root) return num;
    const queue = [];
    queue.push(root);
    while(queue.length){
        let cur = queue.pop();
        // 判断是不是左叶子节点的条件
        if(cur.left && !cur.left.left && !cur.left.right){
            num += cur.left.val;
        }
        cur.left && queue.push(cur.left);
        cur.right && queue.push(cur.right);
    }
    return num;
};

513.找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

• 二叉树的节点个数的范围是 [1,104]
• -231 <= Node.val <= 231 - 1

层序遍历

只需找树最后一层的第一个节点即可，使用队列将树每一层进行遍历，然后不断将第一个节点赋给结果值result，遍历结束，result就是想要的值。

var findBottomLeftValue = function(root) {
   let queue = [];
   let result;
   queue.push(root); // 根节点入队
   while(queue.length){
    let len = queue.length;
    for(let i = 0;i < len;i++){ // 每一层进行遍历
        let node = queue.shift(); 
        if(i === 0) result = node.val; // 找每一层的第一个节点
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
    }
   }
   return result;
};

112.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

• 树中节点的数目在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

回溯

var hasPathSum = function(root, targetSum) {
    if(!root) return false;
    const sum = targetSum;
    const findPath = (root, sum) => {
        if(!root.left && !root.right && sum === 0){
            return true;
        };
        if(!root.left && !root.right) return false;
        if(root.left){
            if(findPath(root.left, sum - root.left.val)) return true;
        }
        if(root.right){
            if(findPath(root.right, sum - root.right.val)) return true;
        }
        return false;
    }
    return findPath(root, sum - root.val);
};

使用flag

定义flag变量，初始为false。

进入递归，值为节点root和sumbi表示当前节点到根节点的总和。

sum不断增加，当sum等于targetSum时，就把flag置为true。随即返回flag即可。

• flag为true，找到路径
• flag为false，没找到

var hasPathSum = function(root, targetSum) {
    if(!root) return false;
    const sum = 0;
    let flag = false; // 全局变量flag标志
    const findPath = (root, sum) => {
        if(!root) return ;
        // 此时sum等于目标总和且为叶子节点，找到了路径,flag置为true
        if(sum === targetSum && (!root.left && !root.right)){
            flag = true;
        }
        // 如果有左节点，左节点进入递归，sum值加上左节点的值
        if(root.left) findPath(root.left, sum + root.left.val);
        // 如果有右节点，右节点进入递归,sum值加上右节点的值
        if(root.right) findPath(root.right, sum + root.right.val);
    }
    // 初始sum加上根节点的值
    findPath(root, sum + root.val);
    return flag;
};

106.从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

分割中序、后序数组

var buildTree = function(inorder, postorder) {
    if(postorder.length === 0) return null;
    let node = postorder[postorder.length - 1]; // 获取后序遍历的最后一个值作为根节点
    let root = new TreeNode(node); // 创建节点
    let index = inorder.indexOf(node); // 获取中序遍历中node所在的位置
    let inLeft = inorder.slice(0, index); // 对中序遍历进行分割，获取以该节点为根的所有左子树
    let inRight = inorder.slice(index+1); // 分割以该节点为根的所有右子树
    let poLeft = postorder.slice(0,inLeft.length); // 对后序遍历进行分割，获取以该节点为根的所有左子树
    let poRight = postorder.slice(inLeft.length,postorder.length - 1); // 对后序遍历进行分割,获取以该节点为根的所有右子树
    root.left = buildTree(inLeft, poLeft); // 将分割好的左子树的中序、后序遍历数组传入函数进行递归
    root.right = buildTree(inRight, poRight); // 将分割好的右子树的中序、后序遍历数组传入函数进行递归
    return root; // 返回根节点
}; 

654.最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 *最大二叉树* 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• nums 中的所有整数 互不相同

获取最大值

每次递归都获取当前数组的最大值，然后根据其在数组中的位置进行分割左子树和右子树，进入递归。

var constructMaximumBinaryTree = function(nums) {
    if(nums.length === 0) return null; // 递归结束条件
    let max = Math.max(...nums); // 获取当前数组的最大值作为根节点
    let index = nums.indexOf(max); // 找出最大节点在当前数组所在的索引
    let left = nums.slice(0,index); // 根据找出的索引进行分割数组，分割左数组
    let right = nums.slice(index+1); // 分割右数组
    let root = new TreeNode(max); // 根据最大值创建根节点
    root.left = constructMaximumBinaryTree(left); // 进入左子树递归
    root.right = constructMaximumBinaryTree(right); // 进入右子树递归
    return root; // 最后返回根节点即可
};

617.合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

• 两棵树中的节点数目在范围 [0, 2000] 内
• -104 <= Node.val <= 104

递归

var mergeTrees = function(root1, root2) {
    if(!root1 && !root2) return null; // 递归结束条件，当root1和root2都为空时，返回null（不能直接一个return，否则返回的是undefined，会报错）
    let node; // 定义节点
    if(root1 && root2){ // 如果root1和root2同时存在，则节点的值为root1.val+root2.val
        node = new TreeNode(root1.val + root2.val);
    }else if(root1 || root2){ // 如果root1和root2只存在一个，则节点的值为存在的那个的值
        let val = root1 ? root1.val : root2.val;
        node = new TreeNode(val);
    }
    node.left =  mergeTrees(root1 ? root1.left : null,root2 ? root2.left : null); // 给node的左节点赋值，需要先判断root1或root2是否为null，因为它们有可能其中一个为空
    node.right = mergeTrees(root1 ? root1.right : null,root2 ? root2.right : null);// 给node的右节点赋值，同样要判断是否为空
    return node; // 返回节点
};

700.二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

• 数中节点数在 [1, 5000] 范围内
• 1 <= Node.val <= 107
• root 是二叉搜索树
• 1 <= val <= 107

递归

设置一个节点值node，初始为null，然后递归寻找匹配的节点，如果找到直接将值赋给node，没找到node值为null，返回node。

var searchBST = function(root, val) {
    let node = null; // 定义node，初始为null
    const findVal = (root, val) => {
        if(!root) return null; // 如果没找到，返回
        if(root.val === val) node = root;  // 找到，则将该节点赋给node
        root.left && findVal(root.left, val); // 不断进行左右子树的递归
        root.right && findVal(root.right, val);
    }
    findVal(root, val);
    return node; // 最后返回node即可
};

二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

var searchBST = function(root, val) {
    if(!root || root.val === val) return root; // 当节点为空或者节点值等于val值时，返回
    if(root.val > val) return searchBST(root.left, val); // 当节点值大于val值，则将节点的左子树进入递归
    if(root.val < val) return searchBST(root.right, val);// 当节点值小于val值，则将节点的右子树进入递归
};

迭代

var searchBST = function(root, val) {
    while(root !== null){ // 循环结束条件——root===Null
        if(root.val > val) root = root.left; // 当节点值大于val值，则将当前节点赋值为它的左孩子
        else if(root.val < val) root = root.right;// 当节点值小于val值，则将当前节点赋值为它的右孩子
        else return root; // 剩下就只有相等的可能，所以直接返回节点
    }
    return null; // 循环结束还没有返回则说明没有找到匹配的节点，返回null
};

98.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

中序遍历

中序遍历二叉树，将节点值存入数组。如果是二叉搜索树，那么数组一定是升序排列的，所以只需要遍历数组看是否升序即可。

var isValidBST = function(root) {
    let result = [];
    // 中序遍历，将所有的值存入数组
    const traversal = (root) => {
        if(!root) return;
        traversal(root.left);
        result.push(root.val);
        traversal(root.right);
    }
    traversal(root);
    // 判断数组是否升序排列
    for(let i = 1;i < result.length;i++){
        if(result[i] <= result[i - 1])return false;
    }    
    return true;
};

501.二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

• 树中节点的数目在范围 [1, 104] 内
• -105 <= Node.val <= 105

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

map辅助

var findMode = function(root) {
    const map = new Map();
    const More = (root) => {
        if(!root) return;
        // 遍历树，将树的值存入map,key 为节点值，val为出现的次数
        if(map.get(root.val)) map.set(root.val, map.get(root.val) + 1);
        else map.set(root.val, 1);
        root.left && More(root.left);
        root.right && More(root.right);
    }
    More(root)
    // 先获取树的根节点值作为最大值
    let max = map.get(root.val);
    // 结果数组
    let rootVal = [];
    for(let [key,value] of map.entries()){
        // 这是为了判断有多个出现次数最大的节点
        if(map.get(key) ===  max){
            rootVal.push(key);
        }
        // 如果值大于max，将结果数组置为空，并将其作为最大值，将其推入结果数组
        if(value > max) {
            rootVal = [];
            max = value;
            rootVal.push(key);
        }
    }
    return rootVal
};

236.二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 [2, 105] 内。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

递归

递归函数：返回当前子树中 p 和 q 的 LCA。如果没有 LCA，就返回 null。

从根节点 root 开始往下递归遍历……

• 如果遍历到 p 或 q，比方说 p，则 LCA 要么是当前的 p（q 在 p 的子树中），要么是 p 之上的节点（q 不在 p 的子树中），不可能是 p 之下的节点，不用继续往下走，返回当前的 p。

• 当遍历到 null 节点，空树不存在 p 和 q，没有 LCA，返回 null。

• 当遍历的节点 root 不是 p 或 q 或 null，则递归搜寻 root 的左右子树：

  • 如果左右子树的递归都有结果，说明 p 和 q 分居 root 的左右子树，返回 root。
  • 如果只是一个子树递归调用有结果，说明 p 和 q 都在这个子树，返回该子树递归结果。
  • 如果两个子树递归结果都为 null，说明 p 和 q 都不在这俩子树中，返回 null。

var lowestCommonAncestor = function(root, p, q) {
    if(root === null || root === p || root === q) return root; // 当遍历越过叶子节点，或者等于p或者q，直接返回
    let left = lowestCommonAncestor(root.left,p,q); // 递归左子节点，获取返回值
    let right = lowestCommonAncestor(root.right,p,q); // 递归右子节点，获取返回值
    if(left === null) return right; // 如果左子节点为空，说明p、q不在左子节点上，返回右子节点；或者同时为空，right为null，等于返回null
    if(right === null) return left; // 如果右子节点为空，说明p、q不在右子节点上，返回右子节点；或者同时为空，left为null，等于返回null
    return root; // 当左右节点都不为空，说明当前节点时p、q的最近公共祖先，返回root
};

530.二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

• 树中节点的数目范围是 [2, 104]
• 0 <= Node.val <= 105

中序遍历

中序遍历二叉搜索树，将每一个值推入数组，所得到的为升序数组。然后循环判断最小差值即可。

var getMinimumDifference = function(root) {
    let res = [];
    const buildArr = (root) => {
        if(root){
            buildArr(root.left);
            res.push(root.val);
            buildArr(root.right);
        }
    }    
    buildArr(root)
    let diff = Infinity;// 定义一个极大值
    for(let i = 1;i < res.length;i++){
        if(diff > res[i] - res[i-1]){  // 判断最小差值
            diff = res[i] - res[i - 1]
        }
    }
    return diff;
};

在递归中判断极小差值。

var getMinimumDifference = function(root) {
    let res = Infinity; // 初始定义一个极大值
    let preNode = null;
    // 中序遍历
    const inOrder = (root) => {
        if(!root) return;
        inOrder(root.left);
        // 判断当前节点值和前一个节点值的差值与res的大小
        if(preNode) res = Math.min(res, root.val - preNode.val);
        preNode = root; // 记录前一个节点值
        inOrder(root.right);
    }
    inOrder(root);
    return res;
};

236.二叉树的最近公共祖先

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

• 树中的节点数将在 [0, 104]的范围内。
• -108 <= Node.val <= 108
• 所有值 Node.val 是 独一无二 的。
• -108 <= val <= 108
• 保证 val 在原始BST中不存在。

递归

var insertIntoBST = function(root, val) {
    if(!root){ // 如果此时为空，说明找到了合适的位置，创建值为val的节点并返回
        let node = new TreeNode(val);
        return node; 
    }
    if(root.val < val) root.right = insertIntoBST(root.right, val); // 如果当前节点的值小于val，则说明val节点应该创建在节点的右侧，进入递归
    else if(root.val > val) root.left = insertIntoBST(root.left, val);// 如果当前节点的值大于val，则说明val节点应该创建在节点的左侧，进入递归
    return root;
};

迭代

var insertIntoBST = function(root, val) {
    if(!root){ //如果根节点为空，创建一个值为val的节点，直接返回
        let node = new TreeNode(val);
        return node;
    }
    let parent = root; // 记录父节点，每次循环都要记录，方便进行赋值
    let cur = root; // 当前节点
    while(cur){ // 循环，寻找适合val的位置
        parent = cur; // 每次循环都要记录当前节点
        if(cur.val > val) cur = cur.left;
        else cur = cur.right;
    }
    let node = new TreeNode(val); // 创建一个值为val的节点
    if(val > parent.val) parent.right = node; // 决定创建的节点该放在哪里
    else parent.left = node;
    return root;
};

235.二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

迭代

二叉搜索树是有顺序的，它是有序树，所有 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。找到的第一个节点就是p和q的公共祖先节点。

var lowestCommonAncestor = function(root, p, q) {
    while(root){
        if(root.val < p.val && root.val < q.val){
            root = root.right;
        }else if(root.val > p.val && root.val > q.val){
            root = root.left;
        }else return root;
    }
    return null;
};

450.删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

• 节点数的范围 [0, 104].
• -105 <= Node.val <= 105
• 节点值唯一
• root 是合法的二叉搜索树
• -105 <= key <= 105

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

递归

var deleteNode = function(root, key) {
    if(!root) return root;
    
    // 获取匹配节点的右子树的最小节点
    let getMin = (node) => {
        while(node.left){
            node = node.left;
        }
        return node;
    }
    if(root.val < key){
        root.right = deleteNode(root.right, key);
    }else if(root.val > key){
        root.left = deleteNode(root.left, key);
    }else{
        // 第一种情况：root只有左子树
        if(root.right === null) return root.left;
        // 第二种情况： root只有右子树
        if(root.left === null) return root.right;
        // 第三种情况：左右子树都存在，这时需要将匹配节点替换成右子树中最小的节点，同事删除右子树中最小的节点
        let min = getMin(root.right);
        root.val = min.val;
        root.right = deleteNode(root.right, min.val);
    }
    return root;
};

669.修剪二叉树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

提示：

• 树中节点数在范围 [1, 104] 内
• 0 <= Node.val <= 104
• 树中每个节点的值都是 唯一 的
• 题目数据保证输入是一棵有效的二叉搜索树
• 0 <= low <= high <= 104

递归

var trimBST = function(root, low, high) {
    if(!root) return root; // 如果节点为空，直接返回节点
    if(root.val < low){ // 如果当前节点的值小于最小边界，则将他及其他左子树全部修建，去右子树中寻找合适的节点，并将其返回
        let right = trimBST(root.right, low, high);
        return right;
    }
    if(root.val > high){// 如果当前节点的值大于最大边界，则将他及其他右子树全部修建，去左子树中寻找合适的节点，并将其返回
        let left = trimBST(root.left, low, high);
        return left;
    }
    root.left = trimBST(root.left, low, high); // 拼接左节点
    root.right = trimBST(root.right, low, high); // 拼接右节点
    return root;
};

108.将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

递归

进行数组划分。

var sortedArrayToBST = function(nums) {
   let traversal = (nums, left, right) => {
    if(left > right) return null;
    let mid = Math.floor((right + left) / 2);// 获取当前数组中间值索引
    let node = new TreeNode(nums[mid]); // 根据索引创建根节点
    node.left = traversal(nums, left, mid - 1); // 将数组的划分的左部分进行递归
    node.right = traversal(nums, mid + 1, right); // 将数组划分的右部分进行递归
    return node;
   }
   return traversal(nums, 0, nums.length - 1);
};

538.把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

• 树中的节点数介于 0 和 104 之间。
• 每个节点的值介于 -104 和 104 之间。
• 树中的所有值 互不相同 。
• 给定的树为二叉搜索树。

递归

var convertBST = function(root) {
    let pre = 0; // 记录前一个节点的值
    const convert = (root) => {
        if(!root) return;
        convert(root.right); // 从右节点开始遍历
        root.val += pre; // 加上前一个节点的值
        pre = root.val; // 记录上一个节点的值
        convert(root.left); // 遍历左子树
    }
    convert(root);
    return root;
};  

迭代

var convertBST = function(root) {
    let pre = 0; // 作用：记录前一个节点的val值
    let cur = root; // cur辅助节点，用于进入循环
    let stack = []; // 栈
    while(cur !== null || stack.length > 0){ // 循环条件，树不为空或者栈长度大于0
        while(cur !== null){ // 首先不断将当前节点的右节点推入数组
            stack.push(cur);
            cur = cur.right;
        }
        cur = stack.pop(); // 取出最右的节点
        cur.val += pre; // 与pre进行相加
        pre = cur.val; // pre记录当前节点的值，用于下次相加
        cur = cur.left; // 搜索cur的左子树
    }
    return root;
};  

回溯

77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

var combine = function(n, k) {
    let res = []; // 结果数组
    let path =  // 表示其中的一种可能
    let backtracking = (n, k, startIndex) => { // startIndex:防止出现重复的组合
        if(path.length === k){ // 递归终止条件：path的长度等于要求的k长度时结束递归
            res.push([...path]);
            return;
        }
        for(let i = startIndex;i <= n;i++){
            path.push(i); // 处理节点
            backtracking(n, k, i+1);  // 进入递归
            path.pop(); // 回溯，撤销处理的节点，进入下次循环
        }
    }
    backtracking(n, k, 1);
    return res;
};

// 剪枝优化
var combine = function(n, k) {
    let res = [];
    let path = [];
    let backtracking = (n, k, startIndex) => {
        if(path.length === k){
            res.push([...path]);
            return;
        }
        // 当for循环选择的起始位置之后的元素个数已经不足需要的元素个数了，那么就没有必要搜索了
        for(let i = startIndex;i <= n-(k-path.length)+1;i++){
            path.push(i);
            backtracking(n, k, i+1);
            path.pop();
        }
    }
    backtracking(n, k, 1);
    return res;
};

216.组合总和|||

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

var combinationSum3 = function(k, n) {
    let res = [];
    let path = [];
    const backTracking = (k, targetSum, startIndex) => { 
        if(path.length === k){ // 当path的长度等于规定的长度时返回
            if(targetSum === 0) res.push([...path]); // 当结果值等于0时，推入数组
            return;
        }
        for(let i = startIndex;i <= 9;i++){
            path.push(i); // 处理结果
            targetSum -= i; // 总和减1
            backTracking(k, targetSum, i + 1); // 递归
            targetSum += i; // 回溯， 撤销处理的节点
            path.pop();
        }

    }
    backTracking(k, n, 1);
    return res;
};

17.电话号码的组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

var letterCombinations = function(digits) {
    const letterMap = ['','','abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']; // 讲电话号码对应的字母写进数组，下标从2开始
    let res = [];
    let path = [];
    if(digits.length === 0) return []; // 容错，当digits的长度为0也就是空时，返回空数组
    const backTracking = (n, k, index) => { // n表示digits,k表示它的长度，也就是需要循环几次，index表示遍历到哪个数字
        if(path.length === k){ // 当path的长度等于k时返回
            res.push(path.join(""));
            return;
        }
        // 每一个数字代表的是不同集合，也就是求不同集合之间的组合
        for(let i of letterMap[n[index]]){  // 遍历传进来的字符串对应的字母，index用于控制哪个数字，不然会重复遍历同一个数字
            path.push(i);
            backTracking(n, k, index + 1);
            path.pop(); // 回溯，撤销上一个结果
        }
    }
    backTracking(digits, digits.length, 0);
    return res;
};

39.组合

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

var combinationSum = function(candidates, target) {
    let res = [];
    let path = [];
    const backTracing = (target, startIndex ) => {
        if(target <= 0){
            if(target === 0)
                res.push([...path])
            return;
        }
        for(let i = startIndex;i < candidates.length;i++){
            path.push(candidates[i]);
            target -= candidates[i];
            backTracing(target, i); // 因为可以取重复值，所以i不加1
            path.pop();
            target += candidates[i];
        }
    }
    backTracing(target, 0);
    return res;
};

40.组合总和

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

与组合不同的是，每一个组合不能重复，且组合里的值也不能重复。

关键点：

1. 要给数组排序
2. 加一条判断if(i - 1 >= startIndex && candidates[i-1] === candidates[i])，符合直接continue

var combinationSum2 = function(candidates, target) {
    let res = [];
    let path = [];
    candidates = candidates.sort();
    const backTracing = (target, startIndex) => {
        if(target <= 0){
            if(target === 0) res.push([...path]);
        return;
        }
        for(let i = startIndex;i < candidates.length;i++){
            if(i - 1 >= startIndex && candidates[i-1] === candidates[i]){
                continue;
            }
            target -= candidates[i];
            path.push(candidates[i]);
            backTracing(target, i + 1);
            target += candidates[i];
            path.pop();
        }
    }
    backTracing(target, 0);
    return res;
};  

131.分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

var partition = function(s) {
    let res = [];
    let path = [];
    const isPalindrome = (s, start, end) => { // 判断是不是回文字符串
        for(let i=start, j=end;i<j;i++,j--){
            if(s[i] !== s[j])   return false;
        }
        return true;
    }
    const backTracing = (startIndex) => {
        if(startIndex === s.length){ //当startIndex等于s.length时，说明已经遍历完一遍了，返回
            res.push([...path]);
            return;
        };
        for(let i = startIndex;i < s.length;i++){
            if(!isPalindrome(s, startIndex, i)) continue; // 如果不是回文字符串，直接跳过当前循环
            path.push(s.slice(startIndex, i+1)); // 否则将回文字符串推入数组
            backTracing(i+1); // 递归
            path.pop(); // 回溯
        }
    }
    backTracing(0);
    return res;
};

78.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

var subsets = function(nums) {
    let res = []
    let path = [];
    const backTracing = (startIndex) => {
        res.push([...path]);
        // 不用写结束条件，当startIndex超过nums.length，不会进入循环
        for(let i = startIndex;i < nums.length;i++){
            path.push(nums[i]);
            backTracing(i+1);
            path.pop();
        }
    }
    backTracing(0);
    return res;
};

90.子集Ⅱ

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

// 因为要去重，所以先将数组升序排列
var subsetsWithDup = function(nums) {
    let res = [];
    let path = [];
    let numsArr = nums.sort();
    const backTracing = (startIndex) => {
        res.push([...path]);
        for(let i = startIndex;i < numsArr.length;i++){
            // 去重，当数组前一个索引和当前索引对应的值相同时，跳过当前循环
            if(i - 1 >= startIndex && numsArr[i-1] === numsArr[i]){
                continue;
            }
            path.push(numsArr[i]);
            backTracing(i+1);
            path.pop();
        }
    }
    backTracing(0);
    return res;
};

491.递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

var findSubsequences = function(nums) {
    let res = [];
    let path = [];
    const backTracking = (startIndex) => {
        if(path.length >= 2){
            res.push([...path]);
        }
        let use = []; // 标记当前层是否有使用过对应的数字
        for(let i = startIndex;i < nums.length;i++){
            if((path.length > 0 && nums[i] < path[path.length - 1]) || use[nums[i]+100]) continue;
            path.push(nums[i]);
            use[nums[i]+100] = true;
            backTracking(i+1);
            path.pop();
        }
    }
    backTracking(0);
    return res;
};

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]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

var permute = function(nums) {
    const res = [];
    const path = [];
    
    const backTracing = (used) => { // 定义used数组，用于判断当前数是否使用过
        if(path.length === nums.length){
            res.push([...path]);
            return;
        }
        for(let i = 0;i < nums.length;i++){ // 因为每个数都要遍历到，所以从0开始遍历
            if(used[i] === true) continue;
            path.push(nums[i]);
            used[i] = true; // 将当前数的索引对应的used置为true，表示使用过
            backTracing(used);
            used[i] = false; // 回溯
            path.pop();
        }
    }
    backTracing([]);
    return res;
};

47.全排序Ⅱ

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：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 <= 8
• -10 <= nums[i] <= 10

var permuteUnique = function(nums) {
    const res = [];
    const path = [];
    let numsArr = nums.sort();
    const backTracing = (used) => { // 定义used数组，用于判断当前数是否使用过
        if(path.length === numsArr.length){
            res.push([...path]);
            return;
        }
        for(let i = 0;i < numsArr.length;i++){ // 因为每个数都要遍历到，所以从0开始遍历
            if(used[i] === true) continue;
            if(i > 0 && numsArr[i - 1] === numsArr[i] && used[i-1]) continue; // 去重
            path.push(numsArr[i]);
            used[i] = true; // 将当前数的索引对应的used置为true，表示使用过
            backTracing(used);
            used[i] = false; // 回溯
            path.pop();
        }
    }
    backTracing([]);
    return res;
};

51.n皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

var solveNQueens = function(n) {
    const res = [];
    // 判断是否有效
    const isVaild = (row,col,chessBoard,n) => {
        // 在同一行不能有
        for(let i = 0;i < row;i++){
            if(chessBoard[i][col] === 'Q') return false;
        }
        // 在45°不能有
        for(let i=row-1,j=col-1;i >= 0 && j >=0;i--,j--){
            if(chessBoard[i][j] === 'Q') return false;
        }
        // 在135°不能有
        for(let i = row - 1,j = col + 1;i >= 0 && j < n;i--,j++){
            if(chessBoard[i][j] === 'Q') return false;
        }
        return true;
    }
     // 将chessBoard二维数组转换为字符串数组
    const changeChessBoard = (chessBoard) => {
        let chessBoardRes = [];
        chessBoard.forEach(row => {
            let str = "";
            row.forEach(col => {
                str += col;
            })
            chessBoardRes.push(str);
        })
        return chessBoardRes;
    }
	// 回溯
    const backTracing = (row, chessBoard) => {
        if(row === n){
            res.push(changeChessBoard(chessBoard));
            return;
        }
        for(let col = 0;col < n;col++){
            if(isVaild(row,col,chessBoard,n)){ // 当前列有效时进入递归
                chessBoard[row][col] = 'Q';
                backTracing(row+1,chessBoard);
                chessBoard[row][col] = '.';
            }
        }
    }
    let chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.'));
    backTracing(0, chessBoard)
    return res;
};

93.复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

var restoreIpAddresses = function(s) {
    const res = [],path = [];
    const backTracing = (i) => {
        let len = path.length; // 获取当前path的长度
        if(len === 4 && i === s.length){ // 因为path推入的是一个ip字段，判断是否为4，且i此时等于s的长度，说明匹配到了合适的ip地址，将其推入结果数组
            res.push(path.join("."));
            return;
        }
        for(let j = i;j < s.length;j++){ // i表示起始位置，j表示字符的截取位置
            let str = s.slice(i,j+1); // 截取字符串
            if(str.length > 1 && str[0] === '0') break; // 如果当前字符串是0开头，且长度大于1，跳出当前循环，如01 
            if(+str > 255 || str.length > 3) break; // 如果str大于255或长度大于3，跳出当前循环
            path.push(str);
            backTracing(j+1); // 进入递归,让j+1，指向字符串的下一个
            path.pop();     
        }
    }
    backTracing(0);
    return res;
};

37.解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

var solveSudoku = function(board) {
    // 判断数独是否有效
    const isValid = (row, col, val, board) => {
        let len = board.length;
        for(let i = 0;i < len;i++){
            if(board[row][i] === val) return false; 
        }
        for(let i = 0;i < len;i++){
            if(board[i][col] === val) return false;
        }
        let startRow = Math.floor(row / 3)*3;
        let startCol = Math.floor(col / 3)*3;
        for(let i = startRow;i < startRow+3;i++){ // 判断数组3×3格是否有效
            for(let j = startCol;j < startCol + 3;j++){
                if(board[i][j] === val) return false;
            }
        }
        return true;
    }
    const backTracing = () => {
        for(let i = 0;i < board.length;i++){
            for(let j = 0;j < board[i].length;j++){
                if(board[i][j] === '.'){ // 仅当当前格子不为.时进入递归
                    for(let val = 1;val <= 9;val++){ // 循环可输入数
                        if(isValid(i, j, `${val}`, board)){ // 当前数有效时，将其赋在对应的索引上
                            board[i][j] = `${val}`; 
                            if(backTracing()) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false; // 都遍历完说明没有匹配的数字，返回false
                }
            }
        }
        return true; // 返回true
    }
    backTracing();
}; 

贪心

455.分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示：

• 1 <= g.length <= 3 * 104
• 0 <= s.length <= 3 * 104
• 1 <= g[i], s[j] <= 231 - 1

解法

将g小孩胃口，s饼干尺寸进行升序排序，从尾开始遍历胃口，用最大尺寸的饼干满足最大胃口的小孩，直到胃口遍历完。

var findContentChildren = function(g, s) {
    let index = 0;
    s.sort((a,b) => a-b);
    g.sort((a,b) => a-b);
    let m = g.length;
    let n = s.length;
    for(let i = m-1,j =n -1;i >= 0;i--){ // 遍历胃口
        if(s[j] >= g[i] && j >= 0){ // 跟饼干尺寸比大小
            index++;
            j--;
        }
    }
    return index;
};

动态规划

509.斐波那契数列

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

动态规划

var fib = function(n) {
    let res = [0,1]; // 记录前两个值
    for(let i = 2;i <= n;i++){ // 从小数开始，遍历到n
        res[i] = res[i-1] + res[i-2]; // 修改n对应下标的数，为前两个数相加
    }
    return res[n];
};

改良，只依赖前两个数据，所以只需要维护前两个数据就可以。

var fib = function(n) {
    if(n <= 1) return n;
    let res = [0,1];
    let sum ;
    for(let i = 2;i <= n;i++){
        sum = res[0] + res[1]; // 维护两个值即可
        res[0] = res[1];
        res[1] = sum;
    }
    return sum;
};

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

动态规划

与斐波那契数列一致。

var climbStairs = function(n) {
    if(n <= 2) return n;
    let pre1 = 1;
    let pre2 = 2;
    let sum = 0;
    for(let i = 3;i <= n;i++){
        sum = pre1 + pre2;
        pre1 = pre2;
        pre2 = sum;
    } 
    return sum;
};

剑指offer 42.连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100

动态规划

var maxSubArray = function(nums) {
    let max = nums[0];
    for(let i = 1;i < nums.length;i++){
        nums[i] += Math.max(nums[i-1], 0);
        max = Math.max(max, nums[i]);
    }
    return max;
};

338.比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

使用Brian Kernighan （比特计算）算法

使用x = x&(x-1)可以将x的二进制数减少一个1，使用循环将计数变量递增计算1的个数即可。

解题

var countBits = function(n) {
    let arr = Array(n+1);
    for(let i = 0;i <= n;i++){
        arr[i] = counts(i);
    }
    return arr;
};
function counts(i){
    let count = 0;
    while(i>0){
        i = i & (i-1);
        count++;
    }
    return count;
}

---

448.找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

输入：nums = [1,1]
输出：[2]

思路：我的思路是使用includes从1到n(数组长度)进行判断，如果不包含，则直接数字i存入新数组

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    const n = nums.length;
    const newNums = [];
    for(let i = 1;i <= n;i++){
        if(!nums.includes(i)){
            newNums.push(i);
        }
    }
    return newNums;
};

官方题解：遍历数组，使用范围之外的数字来表示存在在数组nums中的数字。

var findDisappearedNumbers = function(nums) {
    const n = nums.length;
    for (const num of nums) {
        const x = (num - 1) % n; //这里的n-1代表在序列数组中num本来应该所在的序号，因为num的范围是从1开始的。%n是为了避免碰到重复的数字，num已经加过n了。这样到最后，只有没有出现的数字所在的序号不会被加n。
        nums[x] += n;
    }
    const ret = [];
    //nums.entries()是生成nums的键值队，[0,]
    for (const [i, num] of nums.entries()) {
        if (num <= n) {
            ret.push(i + 1);
        }
    }
    return ret;
};

链接：https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/solutions/601946/zhao-dao-suo-you-shu-zu-zhong-xiao-shi-d-mabl/

例 
for (const num of nums) {
    const x = (num - 1) % n;
    nums[x] += n;
}
	原数组 4,3,2,7,8,2,3,1     			
第一次交换  num = 4 	x=3	4,3,2,15,8,2,3,1      		
第二次交换  num = 3	x=2	4,3,10,15,8,2,3,1     		
第三次交换  num = 10 x=1	4,11,10,15,8,2,3,1   		
第四次交换  num = 15	x=6	4,11,10,15,8,2,11,1          
第五次交换  num = 8	x=7	12,11,10,15,8,2,11,9 		
第六次交换  num = 2	x=1	12,19,10,15,8,2,11,9 		
第七次交换  num = 11	x=2	12,19,18,15,8,2,11,9
第八次交换  num = 10 x=1 12,27,18,15,8,2,11,9
由此可见，8和2没有变化，即它们所在的序列加一就是没有出现的数字

---

461.汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

我的解法

使用blob函数分别将x，y转换成二进制，并将它传给数组返回。然后对它们for循环进行比较。

var hammingDistance = function(x, y) {
    let X = blob(x);
    let Y = blob(y);
    let i = 0,j = 0;//j计算x和y二进制位数不同的个数
    let length = X.length >= Y.length ? X.length : Y.length;
    for(;i < length;i++){
        if(X[i]!=Y[i])
            j++;
    }
    return j;
};
function blob(x){
    let arr = new Array(32);
    arr.fill(0);
    let i = 0,j=0;
    while(x){
        i = x % 2;
        arr[j++] = i;
        x = parseInt(x/2);//js的Number不分整型和浮点型，所以要使用parseInt将/2的结果转为整型。
    }
    return arr;
}

官方

• 移位实现位计数

​ 将x和y进行异或，相同为0，不同为1，这样异或的结果s中为1的便是x和y二进制中不同的地方。然后让最低位和1进行与运算，相同则加一，不同加0，随后让s右移一位，再进行与运算。

var hammingDistance = function(x, y) {
 	let s = x ^ y;
    let count = 0,i;
    while(s>0){
        i = s & 1;
        count+=i;
        s = s>>1;
    }
}

• Brian Kernighan （比特计算）算法

​ s = x ^ y。x和y异或后，所得的s为一个包含1和0的二进制数，如10001101，这样需要循环8次才能获得结果，可以使用Brian Kernighan （比特计算）算法计算s中1的个数，即使用x&(x-1)，每运行一次，s中的1就会减少1个。该算法会删去s中最右侧的1，最终循环的次数即为s二进制表示中1的数量。

var hammingDistance = function(x, y) {
	s = x ^ y;
    for(let i = 0;s > 0;i++){
        s = s & (s-1);
    }
    return i;
}

78.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

20.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

题解：使用栈进行解决，将右括号存储在数组中，然后将字符串一一入栈，如果是左括号则入栈，如果是右括号进行判断，如果跟出栈的符号能对应，则继续循环，否则return false。到最后，如果栈为空，则return true。

var isValid = function(s) {
    let stack = [];//栈
    s = s.split("");//将字符串分割成数组
    let right = [')','}',']'];//将右阔靠存在right数组中
    for(let i = 0;i < s.length;i++){
        if(!right.includes(s[i])){//如果不是右括号则推入栈中
            stack.push(s[i]);
        }else{//不是则进行判断
            switch(s[i]){//跟栈顶出栈的元素进行比较，如果能匹配上，则继续循环，不能就return false
                case ")":
                    if(stack.pop()!='(')
                        return false;
                    break;
                case "}":
                    if(stack.pop()!='{')
                        return false;
                    break;
                case "]":
                    if(stack.pop()!='[')
                        return false;
                    break;
            }
        }

    }
    if(stack.length==0){//最后判断栈的长度，为0则说明全是有效括号，return true
        return true;
    }else{
        return false;//否则，return false
    }
};

169.多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

暴力解法

我的解法：暴力解法，利用set去重获取nums中的唯一值赋给新数组newNums。然后在深拷贝一个新的数组newNum。循环nums，如果nums中的值等于newNum中的值，则newNums加上自己。循环完后再循环newNums，如果它减去newNum中的对应的值再除去newNum对应的值大于n/2的话则返回。

var majorityElement = function(nums) {
    let time = nums.length / 2;
    let newNums = [...new Set(nums)];//去重，获得新数组
    let newNum = JSON.parse(JSON.stringify(newNums));//深拷贝一个新数组
    for(let i = 0;i < nums.length;i++){
        for(let j = 0;j < newNums.length;j++){
            if(nums[i]==newNum[j])//如果值相等
                newNums[j]+=newNum[j];//newNums加上自身
        }
    }
    for(let i = 0;i < newNums.length;i++){
        if((newNums[i]-newNum[i])/newNum[i]>time){//如果减去自身除以自身大于time则返回
            return newNum[i];
        }
    }
};

哈希表

用哈希表统计数组元素中每个元素出现的次数，返回所有统计次数超过n/2的元素。元素作为哈希表的键，出现的次数作为哈希表的值。

var majorityElement = function(nums) {
    let map = new Map();//创建哈希表
    let time = nums.length/2;
    for(let i = 0;i < nums.length;i++){
        if(map.has(nums[i])){//如果map有nums[i],则让次数加一
            map.set(nums[i],map.get(nums[i])+1);
        }else{//如果没有，则添加
            map.set(nums[i],1);
        }
    }
    for(let key of map.keys()){//使用for ... of遍历map的key
        if(map.get(key)>time){//如果key对应的值大于time则返回
            return key;
        }
    }
};

Boyer-Moore 投票算法

记录第一个士兵为winner=nums[i]，然后设置count计数器为0。遍历循环数组，当与winner相同时，count++，不相同，count–，当count为0时，nums[i]重新赋值给winner。这样遍历结束后，winner就是所求的数。

var majorityElement = function(nums) {
    let winner = nums[0];//创建士兵
    let count = 0;//创建计数器
    for(let i = 0;i < nums.length;i++){
        if(winner == nums[i]){//当nums[i]与士兵相同时count++
            count++;
        }else if(count == 0){//减到后面count为0时，winner重新赋值
            winner = nums[i];
            count++;
        }else{//不同时,count--
            count--;
        }
    }
    return winner;
};

“同归于尽消杀法” ：

由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。

1. 遍历数组
2. 第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。
3. 如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主不变，winner 依然是当前这个士兵所属阵营，现存兵力 count 加一；
4. 如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。 此时前方阵营兵力-1, 即使双方都死光，这块高地的旗帜 winner 不变，没有可以去换上自己的新旗帜。
5. 当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，winner 变成这个士兵所属阵营的旗帜，现存兵力 count ++。
6. 就这样各路军阀一直厮杀以一敌一同归于尽的方式下去，直到少数阵营都死光，剩下几个必然属于多数阵营的，winner 是多数阵营。

（多数阵营 51个，少数阵营只有49个，死剩下的2个就是多数阵营的人）

229.多数元素||

暴力解法

var majorityElement = function(nums) {
    let time = nums.length / 3;
    let Element = [];
    let newNums = [...new Set(nums)];
    let newNum = JSON.parse(JSON.stringify(newNums));
    for(let i = 0;i < nums.length;i++){
        for(let j = 0;j < newNums.length;j++){
            if(nums[i]==newNum[j] && nums[i]!=0)
                newNums[j]+=newNum[j];
            else if(nums[i]==newNum[j] && nums[i]==0){
                newNums[j]+=1;
            }
        }
    }

        for(let i = 0;i < newNums.length;i++){
            if(newNum[i] == 0){
                formula = (newNums[i]-newNum[i])/1;
            }else{
                formula = (newNums[i]-newNum[i])/newNum[i];
            }
            if(formula>time){
                Element.push(newNum[i]);
            }
        }
    
    
    return Element;
};

哈希表

用哈希表统计数组元素中每个元素出现的次数，返回所有统计次数超过n/3的元素。元素作为哈希表的键，出现的次数作为哈希表的值。

var majorityElement = function(nums) {
    let time = nums.length / 3;//获取出现次数
    let Element = [];
    let map = new Map();//创建map字典，map键值一一对应
    for(let i = 0;i < nums.length;i++){
        if(map.has(nums[i])){//如果map有nums[i],则让次数加一
            map.set(nums[i],map.get(nums[i])+1);
        }else{//如果没有，则添加
            map.set(nums[i],1);
        }
    }
    for(let o of map.keys()){//使用for ... of遍历map的key
        if(map.get(o)>time){//如果key对应的值大于time则将其加入数组
            Element.push(o);
        }
    }
    return Element;
};

136.只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

异或

题目要求只是用常量额外空间，所以不能使用哈希表，使用哈希表则空间复杂度为O(n)，可以使用异或运算。

​ 异或运算两数相同为0，不同为1。拓展开来，两个不同的数相异或，得到另一个数，当第二次遇到其中一个数时则会还原成另一个数。这用到了异或的交换律和结合律。a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

var singleNumber = function(nums) {
    let single = nums[0];//先获取第一个数
    for(let i = 1;i < nums.length;i++){//i从1开始遍历
        single ^= nums[i];//不断与所有数进行异或，相同为0不同为1，剩到最后的数为只出现一次的数
    }
    return single;
};

哈希表（不考虑空间复杂度）

var singleNumber = function(nums) {
    let map = new Map();
    for(let i = 0;i < nums.length;i++){
        if(map.has(nums[i])){
            map.set(nums[i],map.get(nums[i])+1);
        }else{
            map.set(nums[i],1);
        }
    }
    for(let key of map.keys()){
        if(map.get(key) == 1)
            return key;
    }
};

283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

覆盖

创建一个count变量为0作为数组下标，for …of遍历数组，当数组的值不为0的时候，将当前数组的值赋给以count作为下标的数组，令count++进入下一次循环。随后count的值一定为数组不为0的数字的长度。for循环nums.length-count次，给数组末尾补0。

var moveZeroes = function(nums) {
    let count = 0;
    for(let i of nums){//for...of中的i是数组的value值
        if(i != 0){//此方法是索引从0开始，让数组的不为0的值覆盖为0的值
            nums[count++] = i;
        }
    }
    for(;count<nums.length;count++){
        nums[count] = 0;//想数组末尾补0
    }
};

我的解法

两层循环遍历，当遍历的值为0时，让当前值与后面的值进行交换。

var moveZeroes = function(nums) {
    let count = 0;
    for(let i of nums){
        if(i != 0){
            nums[count++] = i;
        }
    }
    for(;count<nums.length;count++){
        nums[count] = 0;
    }
};

48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

var rotate = function(matrix) {
    let n = matrix.length;
    for (let i = 0; i < Math.floor(n / 2); ++i) {
        for (let j = 0; j < Math.floor((n + 1) / 2); ++j) {
            const temp = matrix[i][j];
            matrix[i][j] = matrix[n - j - 1][i];
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
            matrix[j][n - i - 1] = temp;
        }
    }

};

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

迭代

假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3.

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

function reverseList(head: ListNode | null): ListNode | null {
    let prev = null;
    let curr = head;
    while(curr){
        const next = curr.next;//储存当前节点的下一个节点
        curr.next = prev;//让当前节点的next指向prev
        prev = curr;//prev等于当前节点，进入下次循环
        curr = next;//curr赋值为刚刚暂存的next值
    }
    return prev;    
};

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

数组双指针

将链表的值从头节点开始一一存进数组，然后用双指针从头和末尾去遍历数组进行比对。

function isPalindrome(head: ListNode | null): boolean {
    let arr:Array<number> = [];
    while(head){
        arr.push(head.val);
        head = head.next;
    }
    for(let i = 0,j = arr.length-1;i<arr.length,j>0;i++,j--){
        if(arr[i] != arr[j])
            return false;
    }
    return true;
};

递归

将head用全局变量指针存储，然后创建递归函数，递归会为每一次递归的值创建一个执行上下文栈保留当前状态，当递归到链表的最后会从后往前回退，然后利用这个特性跟全局变量指针进行对比，每一次都让指针指向下一个节点。

let frontPointer ;
function recursivelyCheck (current:ListNode | null):boolean{
    if(current){//判断当前节点是否为空
        if(!recursivelyCheck(current.next)) return false;//递归会一直执行下去，并将变量当前状态存储在执行上下文栈中，直到链表的末尾后函数返回true,!true不执行所以执行下面的语句。
        if(frontPointer.val != current.val) return false;//将全局指针保存的值跟栈返回的状态的值进行对比，如果不同，则会返回false，上一条if语句就会执行，一直返回fals直到执行上下文栈为空
        frontPointer = frontPointer.next;
    }
    return true;

}
function isPalindrome(head: ListNode | null): boolean {
    frontPointer = head;//将头节点用全局变量存储
    return recursivelyCheck(head);
};

快慢指针

1. 找到前半部分链表的尾节点。
2. 反转后半部分链表。
3. 判断是否回文。
4. 恢复链表。
5. 返回结果。

使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

 const reverseList = (head) => {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}
function endOfFirstHalf  (head:ListNode | null):ListNode{
    let fast = head;
    let slow = head;
    while(fast.next != null && fast.next.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
function isPalindrome(head: ListNode | null): boolean {
    let left = head;
    let afterHalf = endOfFirstHalf(head);
    let reverAfter = reverseList(afterHalf);
    while(reverAfter!=null && left!=null){
        if(left.val !== reverAfter.val)
            return false;
        left = left.next;
        reverAfter = reverAfter.next;
    }
    return true;
};

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

迭代

首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。

在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    const Link = new ListNode(-1);
    let prev = Link;
    while(list1!== null && list2!=null){
        if(list1.val <= list2.val){
            prev.next = list1;
            list1 = list1.next;
        }else{
            prev.next = list2;
            list2 = list2.next;
        }
        prev = prev.next;
    }
    prev.next = list1 === null ? list2 : list1;
    return Link.next;
};

141.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

哈希

遍历链表，将链表的每一个节点存入哈希表，最开始判断哈希表中是否有该节点，有的话说明是循环链表，直接返回true。如果循环完哈希表中的值都为1，说明不是循环链表，返回false。

function hasCycle(head: ListNode | null): boolean {
    let map = new Map();
    while(head){
        if(map.get(head)){//先判断哈希表中是否含有该节点，有的话说明是循环链表返回true
            return true;
        }else{
            map.set(head,1);//没有该节点往哈希表中添加该节点
        }
        head = head.next;
    }   
    return false;//循环结束，直到最后都没有返回true说明不是循环链表，返回false
};

快慢指针

「Floyd 判圈算法」（又称龟兔赛跑算法），假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

细节

将fast设置为head.next，将slow设置为head是为了能进入while循环，因为循环条件是slow!=fast，如果他们相等，则无法进入循环。

function hasCycle(head: ListNode | null): boolean {
    if(head === null || head.next === null)
        return false;
    let fast = head.next;
    let slow = head;
    while(slow != fast){
        if(fast === null || fast.next === null)
            return false;
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
};

142.环形链表Ⅱ

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

集合

因为set集合不允许重复，所以遍历链表，将每一个节点存入集合，当集合中存在节点说明是循环链表，返回。如果不是，则while循环结束，返回null。

function detectCycle(head: ListNode | null): ListNode | null {
    let set = new Set();
    while(head){
        if(set.has(head)){
            return head;
        }else{
            set.add(head);
        }
        head = head.next;
    }
    return null;
};

快慢指针

function detectCycle(head: ListNode | null): ListNode | null {
    if (head === null) {
        return null;
    }
    let slow = head, fast = head;
    while (fast !== null) {
        slow = slow.next;
        if (fast.next !== null) {
            fast = fast.next.next;
        } else {
            return null;
        }
        if (fast === slow) {
            let ptr = head;
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;

};

160.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

哈希集合

set集合不允许有重复的值，所以可以先将headA的所有节点存入set集合，然后再循环headB判断，如果有相同的说明他们是相交的起始节点。

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    let set = new Set();
    while(headA != null){
        set.add(headA);
        headA = headA.next;
    }
    while(headB != null){
        if(set.has(headB)){
            return headB;
        }
        headB = headB.next;
    }
    return null;
};

双指针

使用双指针的方法，可以将空间复杂度降至 O(1))。

只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

当链表 headA 和 headB 都不为空时，创建两个指针 pA和 pB，初始时分别指向两个链表的头节点 headA和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

每步操作需要同时更新指针 pA 和 pB。

如果指针 pA 不为空，则将指针 pA移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。

如果指针 pA为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。

当指针 pA和 pB指向同一个节点或者都为空时，返回它们指向的节点或者 null。

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    if(headA === null || headB === null)
        return null;
    let PA = headA,PB = headB;
    while(PA != PB){
        PA = PA ===null ? headB : PA.next;
        PB = PB ===null ? headA : PB.next;
    }
    return PA;
};

617.合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

递归

1. root1为null，root2不为null，返回root2
2. root2为null，root1不为null，返回root1
3. 创建新的树，将root1和root2的val值进行相加，节点的left和right为root1和root2节点的left和right的val值相加（即进入递归）
4. 最后返回树

function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
    if(!root1) return root2;
    if(!root2) return root1;
    let t = new TreeNode(root1.val+root2.val);
    t.left = mergeTrees(root1.left,root2.left);
    t.right = mergeTrees(root1.right,root2.right);
    return t;
};

迭代

226.反转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

递归

采用先序遍历，先判断当前二叉树是否是null，是的话就返回null，遍历交换当前节点的左右节点，然后再递归，将左右节点分别传入函数，最后返回root二叉树。

function invertTree(root: TreeNode | null): TreeNode | null {
    if(!root) return null;
    let left  = root.left;//用变量获取左右节点
    let right = root.right;
    root.left = right;//交换左右节点
    root.right = left;
    invertTree(root.left);//将左右节点传入函数进行递归交换
    invertTree(root.right);
    return root;
};

迭代

采用栈存储当前节点，循环条件是栈的长度不为0。然后定义变量存储出栈的值，判断变量是否为null，是的话跳过本次循环，不是则交换左右节点。将左右节点再推入栈中,直到栈为空。

function invertTree(root: TreeNode | null): TreeNode | null {
    let stack = [];
    stack.push(root);//将根节点存储栈中
    while(stack.length>0){
        let t = stack.pop();//出栈
        if(t == null) continue;//如果t为空，则跳过本次循环，不交换
        let left = t.left;//分别用变量存储左右节点
        let right = t.right;
        t.left = right;//将t的左右节点进行交换
        t.right = left;
        stack.push(t.left);//将交换后的左右节点再推入栈中，进入循环
        stack.push(t.right);
    }
    return root;
};

94.二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

递归

中序遍历，左子树——根节点——右子树，访问左子树和右子树的时候同样可以以这种方式遍历。

function inorderTraversal(root: TreeNode | null): number[] {
    let t:number[] = [];
    //递归遍历函数
    const inorder = (root:TreeNode)=>{
        if(!root)//递归结束条件,节点为空，返回
            return;
        inorder(root.left);//先遍历左节点,所有的状态暂存栈中
        t.push(root.val);//左节点为空后,一一将值推入数组
        inorder(root.right);//遍历右节点
    }
    inorder(root);
    return t;
};

迭代

先一次性将树的左子树的左节点全都推入栈中，随后取出栈顶元素，将其推入数组，然后将当前节点赋值为节点的右孩子，如果右孩子为空，但栈长度仍大于0，进入循环。

function inorderTraversal(root: TreeNode | null): number[] {
    let t1:TreeNode[] = [],t2:number[] = [];
    while(t1.length > 0 || root){//循环条件：数组的长度大于0或者root不为null
        while(root){//先把树的左子树的左节点全都推入栈
            t1.push(root);
            root = root.left;
        }
        root = t1.pop();//栈顶元素出栈
        t2.push(root.val);//将值推入数组
        root = root.right;//root赋值为它的右孩子，若右孩子不为空，则会在下一次循环推入栈中，为空，则会跳过root循环，下一个栈顶元素出栈
    }
    return t2;
};

98.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

递归

设置递归函数，传递三个参数，判断的节点，节点的下界，节点的上界，然后依次递归，如果只单纯比较把节点的左节点和右节点和节点进行比较，那么会出现左右子树中存在值比当前节点小或大的情况，所以比较的同时要把当前节点的上下界一起传递。

function isValidBST(root: TreeNode | null): boolean {
    const isTrue = (root: TreeNode | null,up,lower):boolean => {
        if(!root) return true;
        if(root.val >= up || root.val <= lower)   return false;//如果当前节点大于等于上届，或者小于等于下界，说明不在范围区间内，返回false
        return isTrue(root.left,root.val,lower) && isTrue(root.right,up,root.val);//左节点要比当前节点要小，所以上界传当前节点值，下界为Infinity，右节点要比当前节点大，所以下界传当前节点的值，上界为Infinity
    }
    return isTrue(root,Infinity,-Infinity);
};

迭代

将节点的所有左节点推入栈，然后出栈顶元素，将栈顶元素的值和定义的最小值比较，如果小的话说明不是二叉搜索树，返回false，大则将节点的值赋给最小值，节点的右节点赋给root。在循环结束后，说明遍历完，返回true。

function isValidBST(root: TreeNode | null): boolean {
    let stack = [];
    let inorder = -Infinity;
    while(stack.length > 0 || root){
        while(root){
            stack.push(root);
            root = root.left;//将节点的所有左节点入栈
        }
        root = stack.pop();//出栈顶元素，即最左边的元素
        if(root.val <= inorder) return false;//如果节点的值比定义的最小值小，说明不符合条件按
        inorder = root.val;//大的话进行赋值，进入下次循环
        root = root.right;//节点赋值为右节点
    }
    return true;
};

102.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

迭代

将节点存入队列，遵循先进先出的原则进行层序遍历。因为需要把每一层的节点单独存为一个数组，所以在循环的时候获取队列的长度，一次性处理一层的数据。

var levelOrder = function(root) {
    const queue = [];
    const result = [];
    if (!root) {//如果节点为空，直接返回空队列
        return result;
    }
    queue.push(root);//将节点入队
    while(queue.length !=  0){
        let n = queue.length;//获取当前节点的长度，也就是这一层的节点个数
        let q = [];//存放这一层的节点的数组
        for(let i = 0;i < n;i++){
            const node = queue.shift(); //出队           
            q.push(node.val);//将节点的值推入数组
            if (node.left) queue.push(node.left);//如果节点有左节点，将它推入数组
            if (node.right) queue.push(node.right);//如果节点有右节点，将它推入数组
        }
        result.push(q);//将这一层的节点值的数组推入节点数组中
    }
    return result;
};

子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

递归

使用回溯算法进行解题。

function subsets(nums: number[]): number[][] {
    let path = [];//每一种可能的结果
    let result = [];//最终结果
    const backTracking = (startIndex)=>{
        result.push([...path]);
        if(startIndex >= nums.length)//递归终止条件
            return;
        for(let i = startIndex;i < nums.length;i++){
            path.push(nums[i]);//将nums中的值推入数组
            backTracking(i+1);//令i+1进入递归
            path.pop();//撤销结果
        }
    }
    backTracking(0);//传入索引最小的值0进入递归
    return result;
};

78. 子集 - 力扣（Leetcode）

543.二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

    1
   / \
  2   3
 / \     
4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

递归

假定p是树T中的一个节点，那么p的深度就是节点p的祖先的个数，不包括p本身。这等价于p到根节点有多少条边。这种定义表明，树的根节点的深度为0.

var diameterOfBinaryTree = function(root) {
    let ans = 0;
    const depth = (root)=>{
        if(!root) return 0;
        let L = depth(root.left);
        let R = depth(root.right);
        ans = Math.max(ans,L+R+1);
        return Math.max(L,R)+1;//当前节点较于父节点的深度
    }
    depth(root);
    return ans - 1;
};

75.颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

单指针

var sortColors = function(nums) {
    let len = nums.length;
    let ptr = 0;
    for(let i = 0;i < len;i++){
        if(nums[i] == 0){
            let temp = nums[i];
            nums[i] = nums[ptr];
            nums[ptr] = temp;
            ptr++;
        }
    }
    for(let i = 0;i < len;i++){
        if(nums[i] == 1){
            let temp = nums[i];
            nums[i] = nums[ptr];
            nums[ptr] = temp;
            ptr++;
        }
    }
};

155.最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 104 次

辅助栈

初始化的时候定义一个栈和辅助栈，初始存放Infinity，然后入栈时，普通栈正常入栈，辅助栈则是存放辅助栈栈顶和入栈元素中较小的那个值。出栈的时候，普通栈和辅助栈一起出栈，这样普通栈对应的对小值，在辅助栈中都有体现。

var MinStack = function() {
    this.data = [];
    this.minData = [Infinity];//定义辅助栈，初始存放Infinity
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.data.push(val);
    this.minData.push(Math.min(this.minData[this.minData.length-1],val));//辅助栈存放辅助栈栈顶和入栈元素中较小的一个
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.data.pop();
    this.minData.pop();//两个栈一起出栈
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.data[this.data.length-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.minData[this.minData.length-1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

114.二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

找左子树的最右节点

找root左子树的最右节点，将最右节点的right赋值为root的right，随后将最右节点的前驱节点赋给root的右节点，然后依次循环.

var flatten = function(root) {
    let curr = root;//将root节点赋给curr
    while(curr != null){//循环条件curr不为空
        if(curr.left != null){//如果curr有左节点
            const next = curr.left;
            let predecessor = next;
            while(predecessor.right != null){
                predecessor = predecessor.right;//寻找curr左节点的最右节点
            }
            predecessor.right = curr.right;//将最右节点的右节点赋值为当前节点的右节点
            curr.left = null;//将当前节点的左节点赋null
            curr.right = next;//当前节点的右节点为当前节点的左节点
        }
        curr = curr.right;//将当前节点赋值为当前节点的右节点，依次循环下去
    }
};

114. 二叉树展开为链表 - 力扣（Leetcode）

前序遍历

先前序遍历树，将其每一个节点存入list顺序表。然后for循环，将root的每一个节点赋值为下一个节点。

var flatten = function(root) {
   let list = [];
   const preorder = (root,list)=>{
       if(root){
           list.push(root);
           preorder(root.left,list);
           preorder(root.right,list);
       }
   }
   preorder(root,list);
   for(let i = 1;i < list.length;i++){
       let prev = list[i - 1];//第一次prev为root
       let next = list[i];//next为左子树的第一个节点
       prev.left = null;//将左节点赋值为空
       prev.right = next; //右节点赋值为next
   }
};

121.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

动态规划

var maxProfit = function(prices) {
        let minpice = Infinity;//设置最小值
        let maxprofit = 0;
        for (let i = 0; i < prices.length; i++) {
            if(prices[i] < minprofit){//比较最小值
                minprofit = prices[i];
            }else if(prices[i] - minpice > maxprofit){//当前天数减去最小金额则最大利润转换
                maxprofit = prices[i] - minpice;
            }
        }
        return maxprofit;

};

22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

回溯

var generateParenthesis = function(n) {

    const result = [];//结果集

    const dfs = (str,open,close) => {//三个参数分别是括号组合，(的数量、)的数量
        if(close > open || open > n)    return;//如果)的数量大于(或)的数量大于n，则说明不是有效的括号组合，返回
        if(str.length === 2 * n){//如果str的长度等于2倍的n，则说明括号有效，将其推入结果集
             result.push(str)
             return;
        }  ;
        dfs(str+"(",open+1,close);//递归左括号
        dfs(str+")",open,close+1);//递归右括号
    }
    dfs("",0,0);//初始str为空，open和close都为0
    return result;
};