代码随想录

番风About 4 min

哈希表

二叉树

二叉树的对称

leetcode - 101
代码随想录
可以用递归法, 队列迭代法, 都很巧妙

我一开始看到这题的时候, 想的是层序遍历, 比较每一层数组是否对称, 就显得很不巧妙

这样比较两个 node 是否相等, 结合 Queue 即可完成对比.(把左右同时放入 queue 中并 shift 出, 再递归 push 进)

if (left==null && right ==null){
continue;
}else if(left==null || right ==null){
return false;
}else if(left.val != right.val){
return false;
}

二叉树的深度

最大深度

可以使用前序遍历递归 (用到回溯)
后序遍历递归 (推荐)
层序遍历 (推荐,最简单)

最小深度

使用前序遍历时候注意以下问题!

还是推荐用层序.

平衡二叉树

平衡二叉树：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
这题不能用层序遍历!!

二叉树路径

这种题目要建两个栈, 一个栈记录节点, 一个栈用来记路径, 两个栈同步操作.

构造二叉树

使用前序和中序/后序和中序的数组来确定一棵二叉树 (只有前序和后序是无法确认的)
leetcode-master/problems/0106.从中序与后序遍历序列构造二叉树.md at master · youngyangyang04/leetcode-master

二叉搜索树

二叉搜索树的定义, 对于每一个节点, 左子树内的所有值都小于节点值, 右子树内的所有值都大于所有值.
BST 的重点性质:
使用中序遍历可以获得一个有序数组!!!
经常会遇到比如寻找节点最小绝对值差的这种类型的题,
这里可以额外引入一个指针指向上个变量,
因为是 BST, 所以很多时候可以只做单边判断而不是整树判断.

最小公共祖先

这里需要用到后序的性质, 后续的话从某种意义上来说是从下而上的一个过程.
对于一个节点, 如果他的左子树和右子树都有目标节点的标记, 那么他就是一个最小公共祖先!
同时需要考虑到, 节点本身, 但节点本身就是搜寻目标的时候可以直接返回 (后序的性质)

也可以用更简单的方法, 直接遍历全部路径, 在找公共的 (不推荐,但是思维量最小)

删除 BST 中的节点

需要重构二叉树

裁剪 BST

  let trimBSTImpl = function (root, low, high) {
    if (root == null) return null;
    if (root.val < low) {
      return trimBSTImpl(root.right, low, high);
    }
    if (root.val > high) {
      return trimBSTImpl(root.left, low, high);
    }
    root.left = trimBSTImpl(root.left, low, high);
    root.right = trimBSTImpl(root.right, low, high);
    return root;
  }

leetcode-master/problems/二叉树总结篇.md at master · youngyangyang04/leetcode-master

回溯算法

模板:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

不用考虑剪枝 (暴论!)

全排列

注意

let curNums = [1, 2, 3];
let i = 1;
let length = curNums.length;
let remainCurNums = curNums.slice(0, i) + curNums.slice(i + 1, length);
console.log(remainCurNums); // "12,3" (a string)

在 javascript 中,使用 '+' 运算符号会隐式的把其中一个数组看成字符串

let a = [1, 2] + [2, 3];
console.log(a);// "1,22,3"

javaScript 中的数组加和使用 .concat 或者使用 [...a,...b]

在 javascript 中, 我有个这样的数组: let a = [1,2],[3,4],[5,6](1,2],[3,4],[5,6) 我要查找数组 [3,4] 的 index, 可以用 indexOf 吗

let a = [1, 2], [3, 4], [5, 6](1,%202],%20[3,%204],%20[5,%206); 
let target = [3, 4]; // Use the findIndex method to find the index of [3, 4] 
let index = -1; 
a.forEach((arr, i) => { if (arr[0] === target[0] && arr[1] === target[1]) { index = i; } });