BFS & DFS

chun

2022-4-19

前端笔记数据结构

BFS：广度优先搜索

简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。

DFS：深度优先搜索

简单来说，从根节点出发，然后依次向下继续搜索，直到遇到叶子节点，此时就会向上回溯，继续向为访问过的点继续深度搜索。

基本题型

网易原题

深度遍历tree递归版：

// 深度优先遍历图
// 已访问过的节点集合
const tree = {
	name: 'root',
	children: [
		{
			name: 'c1',
			children: [
				{
						name: 'c11',
					children: []		
					},
					{
						name: 'c12',
					children: []		
				}
			]
		},
		{
			name: 'c2',
			children: [
				{
						name: 'c21',
					children: []		
					},
					{
						name: 'c22',
					children: []		
				}
			]
		}
	]
}

// 深度优先的方式遍历 打印 name
// ['root', 'c1','c11', 'c12', 'c2', 'c21', 'c22']

const visited = new Set();
const list=[];
const dfs = n => {
    visited.add(n.name);
    n.children.forEach((node) =>{
        if(!visited.has(node.name)){
            dfs(node);
        }
    })

};
dfs(tree);
console.log(visited);

深度遍历非递归版：

用栈来模拟递归，注意要从后结点逆序结点入栈

const visited = new Set();
const list=[];
const dfs = n => {
	if(!n) return [];//根结点不存在
    list.push(n);//根节点入栈
	while(list.length){
		let curnode=list.pop();//栈顶出栈，返回visited
		visited.add(curnode.name);
		for(let i=curnode.children.length-1; i>=0; i--){
			list.push(curnode.children[i]);//迭代重点！！从后面结点压入栈中
		}
	}

};
dfs(tree);
console.log(visited);

二叉树最大深度

题目描述：给定一个二叉树，找出其最大深度。

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

链接：力扣-二叉树的最大深度

递归思路：

每次分别遍历左节点,以及右节点,然后对比两者,取最大值
这样子，每次递归的话，深度都加1

时间复杂度：O(n)，其中 nn为二叉树节点的个数。每个节点在递归中只被遍历一次。

var maxDepth = function (root) {
    if (!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

非递归思路:

BFS，广度优先遍历
每一次用一个数组temp保存下一层的所有节点，每次计数器count+1
当temp为空的时候，也就是此时都是叶子节点情况

每次拓展下一层的时候，不同于广度优先搜索的每次只从队列里拿出一个节点，我们需要将队列里的所有节点都拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是当前层的所有节点，即我们是一层一层地进行拓展

时间复杂度：O(n)O(n)，其中 n 为二叉树的节点个数。

/**
 * 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 maxDepth = function (root) {
    if (!root) return 0;
    let count = 0;
	let list=[];
	let max=0;
	list.push(root);
	while (list.length) {
		let temp=[];//重点，存储下一层的所有结点
		max++;//list不为空的情况下+1
		for(let i=0; i<list.length; i++) {//将队列所有结点扩展
			if (list[i].left) temp.push(list[i].left);
			if (list[i].right) temp.push(list[i].right);
		}
		list=temp;//进入下一层结点
	}
	return max;
};

二叉树最小深度

实现原理跟最大深度差不多

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

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

递归版：

注意左子树或右子树为空的情况

/**
 * 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 minDepth = function(root) {
        if(!root) return 0;
    let left=minDepth(root.left);
    let right=minDepth(root.right);
    if(!root.left){//左子树为空的话，只取右子树的深度
        return right+ 1;
    }
    else if(!root.right){//同理
        return left + 1 ;
    }
    return Math.min(left,right) + 1;//左右子树都不为空，找最小
};

非递归版：

套路差不多

var minDepth = function(root) {
    if (!root) return 0;
    let list=[];
    let min=0;
    list.push(root)
    while(list.length){
        let temp =[];
        for(let i=0;i<list.length;i++){//遍历这一层的结点
            if(list[i].left) temp.push(list[i].left);
            if(list[i].right) temp.push(list[i].right);
            if(!list[i].left && !list[i].right)   return min+1;//结点的左右都为null时即为最小深度

        }
        list = temp;//进入下一层结点
        min+=1;
    }
    return min;
};

层序遍历：

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

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

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]
复制代码

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/submissions/

这个题最简单的做法就是BFS
每次遍历一层的时候，把它的子节点依次按顺序保存temp
把子节点的结果作为新的结果，也就是que = temp

var levelOrder = function(root) {
    if (!root) return [];
    let list=[];
    let res=[];
    list.push(root)
    while(list.length){
        let temp =[];
        let Toarray = [];
        for(let i=0;i<list.length;i++){//遍历这一层的结点  
            Toarray.push(list[i].val);  
            if(list[i].left) temp.push(list[i].left);
            if(list[i].right) temp.push(list[i].right);
        }
        res.push(Toarray);
        list = temp;//进入下一层结点
    }
    return res;
};

阅读剩余

作者：chun

链接：https://chun53.top/865.html

文章版权归作者所有，未经允许请勿转载。

THE END