dfs 深度遍历

dfs 深度遍历 多见于 二叉树，但其实不限于此，在岛屿网格问题里也很常见。

二叉树：

递归模板

matrix 矩阵

matrix 和 下面的岛屿数据结构上很像
记忆化的深度遍历：
1）遍历 matrix的每个节点
2）每个节点 dfs 遍历，过程中，记录从每个节点出发最大深度即可
3）每个节点 dfs 遍历，过程中，遇到已经遍历过的节点则直接取

var longestIncreasingPath = function(matrix) {
    let rowLength = matrix.length;
    let cloumnLength = matrix[0].length;
    let max = 1;
    let maxArray = [[0, 0]];
    let map = new Map();
    function walk([row, column]) {
        if (map.has(`${row},${column}`)) {
            return map.get(`${row},${column}`);
        }
        let directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
        let biggerQueue = [];
        for (let [_rowDiff, _columnDiff] of directions) {
            let [newRow, newColumn] = [row + _rowDiff, column + _columnDiff];
            if (0 <= newRow && newRow < rowLength && 0 <= column && column < cloumnLength) { // 在边界内
                if (matrix[newRow][newColumn] > matrix[row][column]) {
                    biggerQueue.push([newRow, newColumn]);
                }
            } else { // 不在边界内
                continue;
            }
        }
        if (biggerQueue.length > 0) {
            let _max = 0;
            let _maxArray = [];
            for (let [newRow, newColumn] of biggerQueue) {
                let _tmp = walk([newRow, newColumn]); // 迭代调用
                if (_max < _tmp.length) { // 后面的操作，可以理解为 后序操作
                    _max = _tmp.length;
                    _maxArray = [[row, column], ..._tmp];
                }
            }
            if (max < _max + 1) {
                max = _max + 1;
                maxArray = _maxArray;
            }
            map.set(`${row},${column}`, _maxArray);
            return _maxArray;
        } else {
            map.set(`${row},${column}`, [[row, column]]);
            return [[row, column]];
        }
    }
    for (let row = 0; row < rowLength; row++) {
        for (let column = 0; column < cloumnLength; column++) {
            walk([row, column]);
        }
    }
    return max;
};

但是结果太差了。

我搞不明白，为什么这么差！
但其实，我第一次在做这道题时，竟然有更高级的做法，
避免无脑去做：
1）找到路径的头，即为局部极小值。
2）从局部极小值出发，去找最长路径

岛屿问题

L200. 岛屿数量 （Easy）

463. 岛屿的周长 （Easy）

695. 岛屿的最大面积 （Medium）

827. 最大人工岛 （Hard）

这位小兄弟的总结非常好：从二叉树的遍历扩展到岛屿遍历，有普适价值。
常见的模板：

var numIslands = function(grid) {
    let count = 0
    for (let row = 0; row < grid.length; row++) {
        for (let column = 0; column < grid[0].length; column++) {
            if (grid[row][column] === '1') { // 找出发点，0 和 走过的都不计入
                count++;
                walkOnIsland(grid, [row, column]); // 把所有走过得陆地标记为 2，避免再找，这样就不需要把单独设置 map,但是会改变输入的grid
            }
        }
    }
    return count;
};
var walkOnIsland = function(island, [row, column]) {
    if (!inIsland(island, [row, column])) {
        return;
    }
    if (island[row][column] === '0' || island[row][column] === '2') {
        return;
    }
    island[row][column] = '2';
    walkOnIsland(island, [row - 1, column]); // up
    walkOnIsland(island, [row, column + 1]); // right
    walkOnIsland(island, [row + 1, column]); // down
    walkOnIsland(island, [row, column - 1]); // left
};
var inIsland = function(island, [row, column]) {
    if (
        (0 <= row && row < island.length) 
        && (0 <= column && column < island[0].length)
    ) {
        return true;
    }
    return false;
}

图

797. All Paths From Source to Target

在图中甚至都可以使用。

var allPathsSourceTarget = function(graph) {
    let map = new Map(); // key 为 node，value 是 node 的下一站能去的节点
    let n = graph.length;
    for (let i = 0; i < n; i++) {
        map.set(i, graph[i]);
    }
    let ans = [];
    function walk(start, path) {
        if (start === n - 1) {
            path.push(n - 1);
            ans.push(path);
            return;
        }
        let nextNodes = map.get(start);
        for (let next of nextNodes) {
            walk(next, [...path, start]);
        }
    }
    walk(0, []);
    return ans;
};

单链表

83. 删除排序链表中的重复元素

var deleteDuplicates = function(head) {
    function dfs(node) {
        if (!node) {
            return;
        }
        while (node.next && (node.val === node.next.val)) { // 前序操作！！
            node.next = node.next.next;
        }
        dfs(node.next);
    }
    dfs(head);
    return head;
};