leetcode算法笔记大全

https://leetcode.cn/circle/discuss/RvFUtj/

数组

Leetcode day 1

刷题内容和建议

704.二分查找

https://leetcode.cn/problems/binary-search/

注意要选择的区间是左闭右闭还是左闭右开，这样才能知道如何选择<=还是<


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    let right = nums.length - 1
    let left = 0
    let mid = Math.ceil((right + left) / 2)
    while (left <= right) {
        if (target > nums[mid]) {
            left = mid + 1
        } else if (target < nums[mid]) {
            right = mid - 1
        } else {
            return mid
        }
        mid = Math.ceil((right + left) / 2)
    }
    return -1
};
console.log(search([-1, 0, 3, 5, 9, 12], 9));

27. 移除元素

https://leetcode.cn/problems/remove-element/

暴力法

/**暴力法
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let tmp = []
    let num = 0
    for(let i = 0;i<nums.length;i++){
        if(nums[i]!=val){
            tmp.push(nums[i])
            num++
        }
    }
    for(let j = 0;j<tmp.length;j++){
        nums[j] = tmp[j]
    }
    return num
};

双指针法


/**双指针法
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums, val) {
    let j = 0
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[j] = nums[i]
            j++
        }

    }
    return j
};

977.有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/

双指针法

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
    let newArr = []
    let left = 0, right = nums.length - 1
    let max
    while (left <= right) {
        let left2 = nums[left] * nums[left]
        let right2 = nums[right] * nums[right]
        if (left2 < right2) {
            max = right2
            right--
        } else {
            max = left2
            left++
        }
        newArr.unshift(max)
    }

    return newArr
};
console.log(sortedSquares([-4, -1, 0, 3, 10]));

Leetcode day 2

刷题内容和建议

209.长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

1.注意要选择的区间是左闭右闭还是左闭右开，这里我选的是左闭右开 2.min可以定义为nums的长度，因为这个最小值不可能大于nums的长度 3.因为当right出去后，left还有往右的可能，可以使得min最小，所以不能一旦right跳出去就跳出循环，要用while循环而不是以right为下标的for循环

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let left = 0//不包括right
    let right = 0
    let sum = 0
    let min = nums.length + 1, num = 0//min可以定义为nums的长度，因为这个最小值不可能大于nums的长度
    while (left <= right && right <= nums.length) {//这里应该看left的值，因为当right出去后，left还有往右的可能，可以使得min最小
        if (sum < target) {
            sum += nums[right]
            right++
            num++
        } else {
            min = min < num ? min : num
            sum -= nums[left]
            left++
            num--
        }
    }
    return min > nums.length ? 0 : min
};

59.螺旋矩阵II

https://leetcode.cn/problems/spiral-matrix-ii/description/

不能通过var arr = new Array(10).fill(new Array(10).fill(0))这样创建二维数组，第一个值赋值的时候第一列所有的值都会被赋值

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function (n) {
    let arr = new Array(n); 
    for (let i = 0; i < arr.length; i++) {
        arr[i] = new Array(n).fill(0); 
    }
    let x = 0, y = 0;
    let val = 1
    function func(x, y, val, n) {
        if (n === 1) {
            arr[x][y] = val
        }
        for (let i = 0; i < n - 1; i++) {
            arr[x][y] = val
            y++
            val++
        }
        for (let j = 0; j < n - 1; j++) {
            arr[x][y] = val
            x++
            val++
        }
        for (let k = 0; k < n - 1; k++) {
            arr[x][y] = val
            y--
            val++
        }
        for (let l = 0; l < n - 1; l++) {
            arr[x][y] = val
            x--
            val++
        }
        if (n - 2 > 0) {

            func(x + 1, y + 1, val, n - 2)
        }
    }
    func(x, y, val, n)
    return arr
};
generateMatrix(3)

58. 区间和（第九期模拟笔试）

https://kamacoder.com/problempage.php?pid=1070

注意这里是acm模式的算法题，不是说只用写个函数出来就行的，要引入readline，读取控制台的输入

function prefixSum() {
    const readline = require('readline');

    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    let inputLines = [];
    rl.on('line', (line) => {
        inputLines.push(line.trim());
    });

    rl.on('close', () => {
        // 读取项数 n
        const n = parseInt(inputLines[0]);

        // 使用前缀和，复杂度控制在 O(1)
        let sum = new Array(n);
        sum[0] = parseInt(inputLines[1]);

        // 计算前缀和数组
        for (let i = 1; i < n; i++) {
            let value = parseInt(inputLines[i + 1]);
            sum[i] = sum[i - 1] + value;
        }

        // 处理区间和查询
        for (let i = n + 1; i < inputLines.length; i++) {
            let [left, right] = inputLines[i].split(' ').map(Number);

            if (left === 0) {
                console.log(sum[right]);
            } else {
                console.log(sum[right] - sum[left - 1]);
            }
        }
    });
}
prefixSum()

44. 开发商购买土地（第五期模拟笔试）

https://kamacoder.com/problempage.php?pid=1044

function func() {
    const readline = require('readline')
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    })
    let inputLines = []
    rl.on('line', function (line) {
        inputLines.push(line.trim())
    })

    rl.on('close', function () {
        let [n, m] = inputLines[0].split(" ").map(Number)
        let c = new Array(n).fill(0)//每一行的和
        let r = new Array(m).fill(0)//每一列的和
        let arr = new Array(n)
        let sum = 0//数组总和
        let min = Infinity//设置最小值的初始值为无限大
        for (let s = 0; s < n; s++) {
            arr[s] = inputLines[s + 1].split(" ").map(Number)
        }
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                c[i] += arr[i][j]
                sum += arr[i][j]
            }
        }
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                r[j] += arr[i][j]
            }
        }
        let sum1 = 0, sum2 = 0
        for (let i = 0; i < n; i++) {
            sum1 += c[i]
            min = min < Math.abs(sum - 2 * sum1) ? min : Math.abs(sum - 2 * sum1)
        }
        for (let j = 0; j < m; j++) {
            sum2 += r[j]
            min = min < Math.abs(sum - 2 * sum2) ? min : Math.abs(sum - 2 * sum2)
        }
        console.log(min);
    })
}
func()

链表

Leetcode day 3

刷题内容和建议

203.移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

错解

1.当出现增删改的时候都是需要创建虚拟结点newHead的
2.如果发现值等于目标删除的结点，删除后不需要再cur = cur.next了，因为这个地方while检验的是cur.next的值，当删除cur.next结点后，cur.next指向的就是下次循环要检验的结点了不需要在cur = cur.next了

/**
 * Definition for singly-lincured list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}
var removeElements = function (head, val) {
    let newHead = new ListNode(0, head)
    let cur = newHead
    while (cur.next != null) {
        if (cur.next.val === val) {
            cur.next = cur.next.next
        }
        cur = cur.next//如果发现值等于目标删除的结点，删除后不需要再cur = cur.next了
    }
    return newHead.next
};
正解
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const dummy = new ListNode(0, head);
    let cur = dummy;
    while (cur.next) {
        if (cur.next.val === val) {
            cur.next = cur.next.next
        }else{
            cur = cur.next
        }
    }
    return dummy.next
    
};

707.设计链表

https://leetcode.cn/problems/remove-element/

暴力法

/**暴力法
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let tmp = []
    let num = 0
    for(let i = 0;i<nums.length;i++){
        if(nums[i]!=val){
            tmp.push(nums[i])
            num++
        }
    }
    for(let j = 0;j<tmp.length;j++){
        nums[j] = tmp[j]
    }
    return num
};

206.反转链表

https://leetcode.cn/problems/squares-of-a-sorted-array/

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let k = head;
    let pre = null
    while(k){
        let l = k
        k = k.next
        l.next = pre
        pre = l
    }
    return pre
};

leetcode day 4

刷题内容和建议

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

https://leetcode.cn/problems/swap-nodes-in-pairs/description/ 注意画图，以防弄错

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let newHead = new ListNode(0,head)
    let i = newHead;
    while(i.next){
        if(i.next.next){
            //交换
            let a1 = i
            let a2 = i.next
            let a3 = i.next.next
            let a4 = i.next.next.next
            a1.next = a3
            a3.next = a2
            a2.next = a4
        }else{
            return newHead.next
        }
        i = i.next.next
    }
    return newHead.next
};

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

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

双指针法

略

递归法

时间复杂度和

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let newHead = new ListNode()
    newHead.next = head
    var i = n
    function func(head, n) {
        if (head === null) {
            return
        } else {
            func(head.next, n)
            i--
        }
        if (i === -1) {
            head.next = head.next.next
        }
        return head

    }
    return func(newHead, n).next

};

160.链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

1.这个地方用!=和!==都是可行的，注意!==是没有类型转换的，是严格比较，而!=是先转换后再比较
2.这个地方是不会出现无限循环的，因为如果两个链表不相交，最后会同时移动到null，这时候A和B相等，跳出循环;而如果两个链表长度相同，他们会在相交结点那里相遇

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {

    let A = headA;
    let B = headB;
    if(A===null||B ===null){
        return null;
    }
    //这个地方是不会出现无限循环的，因为如果两个链表不相交，最后会同时移动到null，这时候A和B相等，跳出循环
    //而如果两个链表长度相同，他们会在相交结点那里相遇
    while (A!==B) {//这个地方用!=和!==都是可行的，注意!==是没有类型转换的，是严格比较，而!=是先转换后再比较
        A = A === null ?headB:A.next;
        B = B === null ?headA:B.next;
    }
    if (A === B) {
        return A
    } else {
        return null
    }
};

142.环形链表II

哈希表法
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    
    const map1 = new Map();
    let top = head
    let num = -1
    while (top) {
        if (map1.has(top)) {
            return top
        } else {
            num++
            map1.set(top, num)
            top = top.next
        }
    }
    return null
};

left走过的结点数为x+y right走过的结点数为x+y+n(y+z) 所以2*(x+y)=x+y+n(y+z) 得x+y=n(y+z)

img

快慢指针法

滑动窗口与双指针（定长/不定长/至多/至少/恰好/单序列/双序列/三指针）

定长滑动窗口

643. 子数组最大平均数 I

https://leetcode.cn/problems/maximum-average-subarray-i/description/

1.不要预设数字是正数，比如下面这个max不能设置为0 2.在第一次滑动窗口长度符合条件的时候，虽然不用进行判定，但是要设置值

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function(nums, k) {
    let max //不能设置为0
    let sum = 0
    let left = 0
    for(let right = 0;right<nums.length;right++){
        sum+=nums[right]
        if(right<k-1){
            continue
        }else if(right === k-1){
            max = sum//在第一次滑动窗口长度符合条件的时候，虽然不用进行判定，但是要设置值
            continue
        }
        sum-=nums[left]
        left++
        max = max>sum?max:sum

    }
    return max/k||sum/k
};

1343. 大小为 K 且平均值大于等于阈值的子数组数目

https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/description/

做判断的时候，不是=，而是===(经常犯错，但如果是编辑器的话是会纠错的)

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} threshold
 * @return {number}
 */
var numOfSubarrays = function(arr, k, threshold) {
    let right = 0,left = 0;
    let sum = 0,num = 0,avg;
    for(;left<arr.length;left++){//这里left和right实际上是写反了，但是不想改了，不影响
        sum+= arr[left]
        if(left<k-1){
            continue
        }else if(left === k-1){//做判断的时候，不是=，而是===
            avg = sum/k
            if(avg>=threshold){
                num++
            }
            continue
        }
        sum -= arr[right]
        right++
        avg = sum/k
        if(avg>=threshold){
            num++
        }
    }
    return num
};

不定长滑动窗口

单序列双指针

双序列双指针

三指针

链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）

一、链表

二、二叉树

学习递归，从二叉树开始。 晕递归的同学，请先看视频讲解【基础算法精讲 09】，欢迎点赞~ 带着问题去做下面的题目：

  1. 一般来说，DFS 的递归边界是空节点。在什么情况下，要额外把叶子节点作为递归边界？
  2. 在什么情况下，DFS 需要有返回值？什么情况下不需要有返回值？
  3. 在什么情况下，题目更适合用自顶向下的方法解决？什么情况下更适合用自底向上的方法解决？

§2.1 遍历二叉树

144. 二叉树的前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

递归法 这里不能return func(root.left)，一旦return就直接跳出func了（当使用递归的时候想清楚小问题，大问题是什么，这样才不会弄错）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let out = []
    function func(root){
        if(root){
            out.push(root.val)
            if(root.left){
                func(root.left)//这里不能return func(root.left)，一旦return就直接跳出func了
            }
            if(root.right){
                func(root.right)
            }
            return out
        }else{
            return out
        }

    }
    func(root)
    return out
};
94. 二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/571418917/

递归法 递归法实质上就是隐形地维护了一个栈

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let out = []
    function func(root) {
        if (root === null) {
            return null
        }
        if (root.left) {
            func(root.left)
        }
        out.push(root.val)
        if (root.right) {
            func(root.right)
        }
    }
    func(root)
    return out

};

迭代法

  1. 迭代法实质上就是把隐形维护的栈显化出来了
  2. 因为我们是不会修改二叉树的结构和值的，所以循环的时候，不是一步步循环的。我们不能想着每次while循环k就只移动一下，来设置循环，这样是不行的
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let k = root
    let stack = []
    let out = []
    while(stack.length||k){//因为我们是不会修改二叉树的结构和值的，所以循环的时候，不是一步步循环的。我们不能想着每次while循环k就只移动一下，来设置循环，这样是不行的
        while(k){
            stack.push(k)
            k = k.left
        }
        k = stack.pop()
        out.push(k.val)
        k = k.right
    }
    return out
};
872. 叶子相似的树

https://leetcode.cn/problems/leaf-similar-trees/description/

  1. 不能使用arr1.join('')===arr2.join('')这样的判断方式，否则[1,2]和[12]会相等，对于数组可以使用toString的方式，比如[1,2,3]用toString方法转换后变成了"1,2,3"

拓展

const arr = [1, 2, 3];
arr.toString(); // "1,2,3"
Object.prototype.toString.call(arr); // "[object Array]"
const obj = { a: 1, b: 2 };
console.log(obj.toString()); // 输出: "[object Object]"

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function(root1, root2) {
    let arr1 = [],arr2 = []
    function dfs(root,arr){
        if(root === null){
            return
        }else{
            if(root.left){
                dfs(root.left,arr)
            }
            if(root.right){
                dfs(root.right,arr)
            }
            if(root.left===null&&root.right===null){
                arr.push(root.val)
            }
        }
    }
    dfs(root1,arr1)
    dfs(root2,arr2)
    return arr1.toString()===arr2.toString()//不能使用arr1.join('')===arr2.join('')这样的判断方式，否则[1,2]和[12]会相等
};
LCP 44. 开幕式焰火
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var numColor = function(root) {
    let map = new Map()
    function func(root){
        if(root){
            if(map.has(root.val)){
                return func(root.left)+func(root.right)
            }else{
                map.set(root.val,1)
                return func(root.left)+func(root.right)+1
            }
        }else{
            return 0
        }
    }
    return func(root)
};
404. 左叶子之和
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
    let sum = 0;
    function func(root){
        if(root){
            if(root.left&&!root.left.left&&!root.left.right){
                sum+=root.left.val
            }
            func(root.left)
            func(root.right)
        }else{
            return 0
        }
    }
    func(root)
    return sum
};

2.2 自顶向下dfs

F129. 求根节点到叶节点数字之和
  1. 在递归里面，如果找到了，仅仅在这里返回true是不够的，因为这里只是在一个dfs里面返回了，但是递归里面有很多个dfs嵌套，你需要从所有的嵌套里面返回出来，因此我们使用了hasFound
var hasPathSum = function(root, targetSum) {
    let sum = 0;
    let hasFound = false; // 添加全局标记

    if(!root){
        return false
    }

    function dfs(node){
        sum += node.val
        
        // 如果是叶子节点且和相等，标记找到并返回
        if(!node.left && !node.right){
            if(sum === targetSum){
                hasFound = true;
                return;//仅仅在这里返回是不够的，因为这里只是在一个dfs里面返回了，但是递归里面有很多个dfs嵌套，你需要从所有的嵌套里面返回出来，因此我们使用了hasFound
            }
        }
        
        // 如果已经找到，就不需要继续搜索了
        if(hasFound) return;

        if(node.left){
            dfs(node.left)    
            sum -= node.left.val
        }
        if(node.right){
            dfs(node.right)
            sum -= node.right.val
        }
    }
    
    dfs(root)
    return hasFound
};
F199. 二叉树的右视图

注意一下两种写法的差别，第一个是在每次递归函数执行结束后再回溯，第二个是在每次递归函数的末尾回溯：

  1. 对于第一种，你必须保证每次一开始执行dfs都有“递”的过程，而不是还没递就算出结果直接返回了，虽然已经知道结果，依然要递
  2. 对于第二种，要保证遇到每次dfs执行都要执行要末尾进行“归”，而不是还没归就直接返回了，虽然已经知道结果，依然要归，而不是直接返回 总结：两种解法都是一样的，是正确的，难度也是一样的
var rightSideView = function(root) {
  let out = []
  let level = 0
  function dfs(node){
    level++
    if(node===null){
        return
    }
    out[level-1] = node.val
    dfs(node.left)
    level--
    dfs(node.right)
    level--
  }
  dfs(root)
  return out
};

var rightSideView = function(root) {
    let out = []
    let level = 0
    
    if(!root) return out
    
    function dfs(node){
        if(node === null){
            return
        }
        
        // 进入下一层
        level++
        
        // 更新当前层的值（不管是否已存在，都覆盖）
        out[level-1] = node.val
        
        // 先左后右遍历
        dfs(node.left)
        dfs(node.right)
        
        // 回溯时层数减一
        level--
    }
    
    dfs(root)
    return out
};
O1315. 祖父节点值为偶数的节点和

dfs不一定只能只有一个参数，也可以传多个参数：这一题我写对了，用的是每次遍历到偶数结点都会去查询孙子结点是否存在，如果存在则加入结果中，但是这样的复杂度很高，这里标答给出的解法值得学习，dfs不一定只能只有一个参数，也可以传多个参数

var sumEvenGrandparent = function(root) {
  let ans = 0;

  const dfs = (grandParent, parent, node) => {
    if(!node) {
      return ;
    }

    if(grandParent.val % 2 === 0) {
      ans += node.val;
    }

    dfs(parent, node, node.left);
    dfs(parent, node, node.right);
  }

  if(root.left) {
    dfs(root, root.left, root.left.left);
    dfs(root, root.left, root.left.right);
  }

  if(root.right) {
    dfs(root, root.right, root.right.left);
    dfs(root, root.right, root.right.right);
  }

  return ans;
};

§2.3 自底向上 DFS

O100. 相同的树

这里灵神的解法很简洁，关键要找到递归结束的条件，就是有任何一个节点为空，则返回false，然后递归判断左右子树是否相同

var isSameTree = function (p, q) {
    if (p === null || q === null) {
        return p === q;
    }
    return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
F110. 平衡二叉树
  1. 这里我一开始没写出来，主要是对平衡二叉树的理解错了，平衡二叉树是指该树所有节点的左右子树的高度相差不超过 1。直接可以按照这个定义来写程序，不要想多了。
  2. 这里灵神的解法很妙，当发现不是平衡二叉树的时候，直接返回-1，然后父递归看到-1，也返回-1，减少不必要的递归。
  3. 不要把else后面的大括号打成小括号
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    function dfs(node){
        if(node===null){
            return 0
        }else{
            if(!node.left&&!node.right){
                return 1
            }else{
                let a = dfs(node.left)
                if(a===-1){
                    return -1
                }
                let b = dfs(node.right)
                if(b===-1){
                    return -1
                }
                if(Math.abs(a-b)>1){
                    return -1
                }
                return Math.max(a,b)+1
            }
        }
    }
    return dfs(root)!=-1
};

三、一般树

四、回溯

回溯三问： 当前操作？ 子问题？ 下一个子问题？

§4.1 入门回溯

F17. 电话号码的字母组合
  1. slice不会改变原数组，从开始索引到结束索引（不包括结束索引）的元素，字符串也可以用slice方法，splice会改变
const fruits = ["Apple", "Banana", "Cherry", "Date", "Elderberry"];
const removed = fruits.splice(1, 2); // 从索引1开始，删除2个元素
console.log(removed); // 输出: ["Banana", "Cherry"]
console.log(fruits); // 输出: ["Apple", "Date", "Elderberry"]
  1. if 条件判断中，使用==或者===，不要用=，这里经常出错
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    let map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    if(digits.length===0){
        return []
    }
    let len = digits.length
    let ans = []
    let path = []
    function dfs(i){
        if(i===len){
            ans.push(path.join(''))
            return
        }
        let tmp = map[Number(digits[i])]
        for(let j = 0 ;j<tmp.length;j++){
            path[i] = (tmp[j])
            dfs(i+1)
        }
    }
    dfs(0)
    return ans
};
Last Updated:
Contributors: namewyf