深度优先搜索 Depth First Search

[yijinc]

深度优先搜索 Depth First Search

深度优先搜索算法（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。

这个算法可能是前端最需要了解和最简单的算法了，html文档结点本身就是一颗树（dom树），React 虚拟dom也是树结构，webpack 的文件依赖为图结构，他们内部都用到了 dfs

下面是个人整理的学习笔记

二叉树的遍历

• leetcode 94. 二叉树的中序遍历
• leetcode 144. 二叉树的前序遍历
• leetcode 145. 二叉树的后序遍历

function dfs(root: TreeNode | null): number[] {
    if (!root) return [];
    const array = [];
    // 左
    array.push(...dfs(root.left))
    // 中
    array.push(root.val);
    // 右
    array.push(...dfs(root.right))
    return array;
};

不同顺序的遍历只需更换push 顺序就好

根节点到叶子节点的路径/深度

• leetcode 112. 路径总和
• leetcode 104. 二叉树的最大深度
• leetcode 129. 求根节点到叶节点数字之和
• leetcode 257. 二叉树的所有路径

// 二叉树的所有路径
function binaryTreePaths(root: TreeNode | null): number[] {
    const results = [];
    const dfs = (node: TreeNode, path: number[] = []) => {
        if (node === null) return;
        path.push(node.val);
        if (node.left === null && node.right === null) { // isLeaf
            results.push([...path]);
            return;
        }
        dfs(node.left, [...path]);
        dfs(node.right, [...path]);
    }
    dfs(root, []);
    return results;
};

矩阵网格问题

• leetcode 130. 被围绕的区域
• leetcode 200. 岛屿数量
• leetcode 463. 岛屿的周长
• leetcode 695. 岛屿的最大面积

/**
* 例
* [leetcode 463. 岛屿的周长](https://leetcode.cn/problems/island-perimeter/)
* 岛屿的周长就是岛屿方格和非岛屿方格相邻的边的数量
* 每当在 DFS 遍历中，从一个岛屿方格走向一个非岛屿方格，就将周长加 1
* */
function islandPerimeter(grid: number[][]): number {
    const rows = grid.length;
    const cols = grid[0].length;
    const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));

    const dfs = (row: number, col: number) => {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return 1; // 越界
        }
        if (grid[row][col] === 0) {
            return 1; // 水域
        }
        if (visited[row][col]) {
            return 0;
        }
        visited[row][col] = true;
        return dfs(row - 1, col) // 上
            + dfs(row + 1, col)  // 下
            + dfs(row, col - 1)  // 左
            + dfs(row, col + 1); // 右
    };

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 1) {
                return dfs(i, j);
            }
        }
    }
    return 0;
};

[yijinc]

插个眼👀

[yijinc]

二叉树的遍历

• leetcode 94. 二叉树的中序遍历
• leetcode 144. 二叉树的前序遍历
• leetcode 145. 二叉树的后序遍历

function dfs(root: TreeNode | null): number[] {
    if (!root) return [];
    const array = [];
    // 左
    array.push(...dfs(root.left))
    // 中
    array.push(root.val);
    // 右
    array.push(...dfs(root.right))
    return array;
};

不同顺序的遍历只需更换push 顺序就好