【js】-【DFS、BFS应用】-学习笔记

1 二叉树的遍历-递归-DFS

// 所有遍历函数的入参都是树的根结点对象
function preorder(root) {
    
    // 递归边界，root 为空
    if(!root) {
    
        return 
    }
     
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
    // 递归遍历左子树 
    preorder(root.left)  
    // 递归遍历右子树 
    preorder(root.right)
}

2 二叉树的层序遍历-BFS

function BFS(root) {
    
    const queue = [] // 初始化队列queue
    // 根结点首先入队
    queue.push(root)
    // 队列不为空，说明没有遍历完全
    while(queue.length) {
    
        const top = queue[0] // 取出队头元素 
        // 访问 top
        console.log(top.val)
        // 如果左子树存在，左子树入队
        if(top.left) {
    
            queue.push(top.left)
        }
        // 如果右子树存在，右子树入队
        if(top.right) {
    
            queue.push(top.right)
        }
        queue.shift() // 访问完毕，队头元素出队
    }
}
BFS(root) //执行BFS

3 给定一个没有重复数字的序列，返回其所有可能的全排列

https://mp.csdn.net/mp_blog/creation/success/124684440

示例：   
输入: [1,2,3]
输出: [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

// 入参是一个数组
const permute = function(nums) {
    
  // 缓存数组的长度
  const len = nums.length
  // curr 变量用来记录当前的排列内容
  const curr = []
  // res 用来记录所有的排列顺序
  const res = []
  // visited 用来避免重复使用同一个数字
  const visited = {
    }
  // 定义 dfs 函数，入参是坑位的索引（从 0 计数）
  function dfs(nth) {
    
  
      # 若遍历到了不存在的坑位（第 len+1 个），则触碰递归边界返回
      if(nth === len) {
    
          // 此时前 len 个坑位已经填满，将对应的排列记录下来
          res.push(curr.slice())
          return 
      }
      // 检查手里剩下的数字有哪些
      for(let i=0;i<len;i++) {
    
          // 若 nums[i] 之前没被其它坑位用过，则可以理解为“这个数字剩下了”
          if(!visited[nums[i]]) {
    
              # 给 nums[i] 打个“已用过”的标
              visited[nums[i]] = 1
              // 将nums[i]推入当前排列
              curr.push(nums[i])
              // 基于这个排列继续往下一个坑走去
              dfs(nth+1) 
              // nums[i]让出当前坑位
              curr.pop()
              // 下掉“已用过”标识
              visited[nums[i]] = 0
          }
      }
  }
  # 从索引为 0 的坑位（也就是第一个坑位）开始 dfs
  dfs(0)
  return res
};

res.push(curr.slice()) 而不是简单的 res.push(curr) 。为什么这样做？因为全局只有一个唯一的 curr ， curr 的值会随着 dfs 的进行而不断被更新。 slice 方法的作用是帮助我们拷贝出一个不影响curr正本的副本，以防直接修改到curr的引用。

4 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集

https://mp.csdn.net/mp_blog/creation/success/124684440

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

const combine = function(n, k) {
    
   // 初始化结果数组
    const res = []   
    // 初始化组合数组
    const subset = []
    // 进入 dfs，起始数字是1
    dfs(1)  

    // 定义 dfs 函数，入参是当前遍历到的数字
    function dfs(index) {
    
        if(subset.length === k) {
    
            res.push(subset.slice())
            return 
        }
        // 从当前数字的值开始，遍历 index-n 之间的所有数字
        for(let i=index;i<=n;i++) {
    
            // 这是当前数字存在于组合中的情况
            subset.push(i) 
            // 基于当前数字存在于组合中的情况，进一步 dfs
            dfs(i+1)
            // 这是当前数字不存在与组合中的情况
            subset.pop()
        }
    }
    // 返回结果数组
    return res 
};

function allSubsets(arr){
    
	let res = [[]];
	for(let i = 0; i < arr.length; i++){
    
		const tempRes = res.map(subset => {
    
			const one = subset.concat([]);
			one.push(arr[i]);
			return one;
		})
		res = res.concat(tempRes);
	}
	return res;
}