图和树遍历策略

图和树遍历的两大核心算法

维度	深度优先搜索 (DFS)	广度优先搜索 (BFS)
核心思想	“一条路走到黑”，走不通再回溯	“层层推进”，由近及远遍历
数据结构	栈（递归调用栈或显式栈）	队列
空间复杂度	$O(h)$ ，h 为树高/搜索深度	$O(w)$ ，w 为最大层宽度
最优性	❌ 不保证找到最短路径	✅ 无权图中保证最短路径
适用场景	路径枚举、连通性、回溯、拓扑排序	最短路径、层序遍历、多源扩散

深度优先搜索 (DFS)

核心思想：沿着一条路径一直走到尽头，再回溯探索其他路径。依赖栈（递归本质上就是调用栈）。

import java.util.*;

public class DFS {

    // ===== 1. 二叉树 DFS（递归）=====
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    // 前序遍历: 根 → 左 → 右
    public static void preOrder(TreeNode node) {
        if (node == null) return;
        System.out.print(node.val + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    // 中序遍历: 左 → 根 → 右（BST中输出有序序列）
    public static void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.val + " ");
        inOrder(node.right);
    }

    // 后序遍历: 左 → 右 → 根
    public static void postOrder(TreeNode node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + " ");
    }

    // ===== 2. 图 DFS（邻接表 + visited 数组）=====
    static Map<Integer, List<Integer>> graph = new HashMap<>();
    static boolean[] visited;

    public static void dfsGraph(int node) {
        visited[node] = true;
        System.out.print(node + " ");
        for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
            if (!visited[neighbor]) {
                dfsGraph(neighbor);
            }
        }
    }

    // ===== 3. 迷宫/网格 DFS（四方向）=====
    static int[][] grid;
    static boolean[][] seen;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static boolean dfsGrid(int x, int y, int targetX, int targetY) {
        if (x == targetX && y == targetY) return true;
        seen[x][y] = true;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 0 && nx < grid.length
             && ny >= 0 && ny < grid[0].length
             && !seen[nx][ny] && grid[nx][ny] == 0) {
                if (dfsGrid(nx, ny, targetX, targetY)) return true;
            }
        }
        return false;
    }

    // ===== 4. 迭代 DFS（用显式栈，避免栈溢出）=====
    public static void dfsIterative(Map<Integer, List<Integer>> g, int start, int n) {
        boolean[] vis = new boolean[n];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (vis[node]) continue;
            vis[node] = true;
            System.out.print(node + " ");
            for (int neighbor : g.getOrDefault(node, Collections.emptyList())) {
                if (!vis[neighbor]) stack.push(neighbor);
            }
        }
    }
}

题目：

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

树节点结构：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

DFS递归解法

public int maxDepth(TreeNode root) {
    if(root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

DFS迭代解法（用栈模拟递归）

class Pair {
    TreeNode node;
    int depth;

    Pair(TreeNode node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Stack<Pair> stack = new Stack<>();
    stack.push(new Pair(root, 1));

    int maxDepth = 0;

    while (!stack.isEmpty()) {
        Pair cur = stack.pop();

        maxDepth = Math.max(maxDepth, cur.depth);

        if (cur.node.left != null) {
            stack.push(new Pair(cur.node.left, cur.depth + 1));
        }

        if (cur.node.right != null) {
            stack.push(new Pair(cur.node.right, cur.depth + 1));
        }
    }

    return maxDepth;
}

BFS解法

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    int depth = 0;

    while (!queue.isEmpty()) {

        int size = queue.size();

        for (int i = 0; i < size; i++) {

            TreeNode node = queue.poll();

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        depth++;
    }

    return depth;
}

三种方法对比

方法	数据结构	时间复杂度	空间复杂度
DFS递归	系统调用栈	O(n)	O(h)
DFS迭代	Stack	O(n)	O(h)
BFS层序	Queue	O(n)	O(w)

广度优先搜索 (BFS)

import java.util.*;

public class BFS {

    // ===== 1. 二叉树 BFS（层序遍历）=====
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();          // 当前层的节点数
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left  != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }

    // ===== 2. 图 BFS（最短路径，无权图）=====
    public static int[] bfsShortestPath(Map<Integer, List<Integer>> graph,
                                        int start, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);          // -1 表示未访问
        dist[start] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[node] + 1;
                    queue.offer(neighbor);
                }
            }
        }
        return dist;  // dist[i] = start 到节点 i 的最短距离
    }

    // ===== 3. 网格 BFS（最短步数）=====
    public static int bfsGrid(int[][] grid, int[] start, int[] end) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0], start[1], 0}); // {row, col, steps}
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1], steps = cur[2];

            if (x == end[0] && y == end[1]) return steps;

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
                 && !visited[nx][ny] && grid[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny, steps + 1});
                }
            }
        }
        return -1; // 不可达
    }

    // ===== 4. 多源 BFS（同时从多个起点出发）=====
    public static int[][] multiSourceBFS(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);

        Queue<int[]> queue = new LinkedList<>();
        // 把所有源点同时入队
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] == 1) { dist[i][j] = 0; queue.offer(new int[]{i, j}); }

        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d], ny = cur[1] + dy[d];
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
                 && dist[nx][ny] == Integer.MAX_VALUE) {
                    dist[nx][ny] = dist[cur[0]][cur[1]] + 1;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
        return dist;
    }
}