算法-掘金小册

https://juejin.cn/book/6844733800300150797/section/6844733800358871054

滑动窗口问题。
本质：
- 队列中保存的是原数组中成员的下标；
- 下标的值，一定是从小到大的顺序放置的；
- 下标对应原数组的值，一定是从大到小放置的；
- 总结一个特点：队列中的成员，其值是原数组对应的下标；下标由小到大排列，而对应的值正好从大到小排列。

滑动窗口：为什么只查看队头就可以确定当前窗口的有效性？先看这个队列的两个特点：

队列是 “大 -> 小” 排列的；
队列若有较大值进入队列，只能从队尾进入，抛弃掉比他小的值。
这些被抛弃的值，在原数组中“更靠前”，也就是说元素下标更小。

为什么只检查最后一个值？

若当前刚超出窗口范围的值 A 是目前最大的，那么这个值就是队列中最后的一个值；
若当前刚超出窗口范围的值 A 不是最大的，那么最大的值进入时，A 已经被抛弃了。

https://juejin.cn/book/6844733800300150797/section/6844733800358871048

子集问题

DFS 深度优先遍历，就是二叉树的先、中、后序遍历，三种都是深度优先。
BFS 广度优先遍历，就是二叉树的层序遍历；

子集问题使用深度优先遍历

每一节点的左值、右值，分别是 “取值” 和 “不取值”。
节点本身并没有值，意思是遍历到节点本身，并不会有取值的动作，节点本身的概念并不重要。
要取的值不是节点本身，而是节点所属的层级，每一层代表一个数值。
- 比如 [3, 5, 8]，分别对应了第一层 3，第二层 5，第三层8。

所以，这里为什么会比较难理解，主要是因为节点本身并没有值，而所要的值是层级。理解到这一点就OK了。

// 先序遍历
function preorder(node) {
  //边界：节点不存在
  if (!node) return;
  //取值，节点所在值
  console.log("current value: ", node.val);
  //先遍历左边
  preorder(node.left);
  //后遍历后边
  preorder(node.right);
}

preorder(tree);

// 子集-DFS
var subsets = function(nums) {
  if (!nums || !nums.length) return;
  const res = [];
  const cur = [];
  dfs(0);
  return res;


  // 传入的不是节点，而是层数
  function dfs(index) {
    //边界：达到最后一层，把本次遍历结果放到 res 中，停止向下遍历
    if (index === nums.length) {
      res.push(cur.slice())
      return;
    }

    //先遍历左边（取值、下一层）
    cur.push(nums[index]);
    dfs(index+1);

    //后遍历后边（不取值、下一层）
    cur.pop()
    dfs(index+1);
  }
}