基础算法：深广度优先遍历及相关题目

深度优先遍历

通常采用方法递归实现，主要思路是找到一条路后一头钻到底（符合递归方法中只有触底return后，才会执行后续语句）（堆栈也可实现）

广度优先遍历

通常采用队列辅助实现，主要思路是遇到一个节点后，将其周遭所有符合条件的节点都记录起来，逐个处理。

岛屿数量

岛屿定义：数组由1 0组成，一整片1即为一个岛屿。
①深度优先遍历：

public int numIslands(char[][] grid) {
        int res = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    res++;
                }
            }
        }

        return res;
    }

    public void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }

使用递归思路，遍历地图上所有格子，每当遇到一个1数值，深度遍历将其连接的1全部标记（将走过的格子值设置为0即可），后续遍历就可以无视走过的格子。
需要注意对边界的判断需要优先于值判断。

②广度优先遍历：

public int numIslands(char[][] grid) {
        int res = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    res++;
                }
            }
        }

        return res;
    }
public void bfs(char[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {i, j});
        while (!queue.isEmpty()) {
            int[] cur = queue.remove();
            int row = cur[0];
            int col = cur[1];
            if (row < grid.length && col < grid[0].length && row >= 0 && col >= 0 && grid[row][col] == '1') {
                grid[row][col] = '0';
                queue.add(new int[] {row + 1, col});
                queue.add(new int[] {row - 1, col});
                queue.add(new int[] {row, col + 1});
                queue.add(new int[] {row, col - 1});
            }
        }
    }

遍历全部格子，遇到1时开始遍历：（深度使用函数递归，广度使用队列辅助）
队列记录所有有延展可能性的格子，每次d出一个进行判断，若在值为1，说明还有可能扩展，则标记后将其相邻格子加入队列，以便后续判断。

省份数量

二维数组i,j值对应城市i与城市j是否相连，相连则属于同一个省份。
①深度优先遍历

public int findCircleNum(int[][] isConnected) {
        int provinces = 0;
        boolean[] visited = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                dfs(isConnected, i, visited);
                provinces++;
            }
        }

        return provinces;
    }

    public void dfs(int[][] isconnected, int i, boolean[] visited) {
        for (int j = 0; j < isconnected.length; j++) {
            if (isconnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(isconnected, j, visited);
            }
        }
    }

从每个城市单独出发去查找其与其他城市的连接性，在遍历过城市后也需要标记（创建visited数组记录）；主函数中的循环是查找基准城市（可看作i），在方法内再向其余城市发散判断连接（可连接的城市看作j），标记后再以j城市进行发散。

②广度优先遍历

public int findCircleNum(int[][] isConnected) {
        int provinces = 0;
        boolean[] visited = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                bfs(isConnected, i, visited);
                provinces++;
            }
        }

        return provinces;
    }
public void bfs(int[][] isconnected, int i, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        while (!queue.isEmpty()) {
            Integer city = queue.remove();
            visited[city] = true;
            for (int j = 0; j < isconnected.length; j++) {
                if (isconnected[city][j] == 1 && !visited[j]) {
                    queue.add(j);
                }
            }
        }
    }

依旧用队列辅助遍历，主函数内选基准城市，在方法内开始发散遍历，每次将所有与基准城市相连的城市标记并加入队列，后续不断d出重复上述 *** 作即可。

上述两题都是每次碰到所需区域就将结果+1，主要处理都是在将相关区域进行标记处理，类似第一题，经过标记处理后，保证每次遇到1即为新的岛屿。

填充每个节点的下一个右侧节点指针 II

题目给出一个树，目的是在每一层横向加一个链表指向。

public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            Node pre = null;

            for (int i = 0; i < size; i++) {
                Node remove = queue.remove();
                if (pre != null) {
                    pre.next = remove;
                }
                pre = remove;
                if (remove.left != null) {
                    queue.add(remove.left);
                }
                if (remove.right != null) {
                    queue.add(remove.right);
                }
            }
        }
        return root;
    }

既然是横向加链表，第一个想到广度优先遍历，在本次的广度优先仍然使用队列先入先出辅助实现，但需要进行切换行的判断，每到新行都需要重新记录行链表的头结点（代码中每次取的size就是每一行包含的节点数，那么每次遍历size个节点就是每次遍历一行；这点清楚后，每一行头结点的清楚在for遍历前进行即可），边向右遍历边记录。

另一棵树的子树

判断树中是否包含目标子树。

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return bfs(root, subRoot);
    }

    private boolean bfs(TreeNode sTree, TreeNode tTree) {
        if (sTree == null) {
            return false;
        }
        return check(sTree, tTree) || bfs(sTree.left, tTree) || bfs(sTree.right, tTree);
    }

    private boolean check(TreeNode sTree, TreeNode tTree) {
          if (sTree == null && tTree == null) {
              return true;
          }
          if (sTree == null || tTree == null || sTree.val != tTree.val) {
              return false;
          }

          if (sTree.val == tTree.val) {
              return check(sTree.left, tTree.left) && check(sTree.right, tTree.right);
          }
          return false;
    }

持续深度遍历，每次遍历都进行判断：
两者都为空：符合子树条件，并且说明探到底后完全相同，可以返回。
某一方为空：不符合条件
两节点值不同：不符合条件
值相同时：进行左右叶子结点的判断。