算法的解题模式Ⅳ

10. 二叉树遍历（Binary Tree Traversal）

二叉树遍历是指按照某种顺序依次访问二叉树中的每个节点，使得每个节点仅被访问一次。

前序遍历：根 -> 左 -> 右

中序遍历：左 -> 根 -> 右

后序遍历：左 -> 右 -> 根

示例： 输入：root = [1, null, 2, 3] 输出：[1, 3, 2] 解释： 中序遍历按照左、根、右的顺序访问节点。 可使用递归或栈来按此顺序遍历树。

 力扣相关题目：

257. 二叉树的所有路径

230. 二叉搜索树中第 K 小的元素

124. 二叉树中的最大路径和

11.深度优先搜索（DFS）

深度优先搜索遍历会沿着树的深度尽可能深地访问节点，直到无法继续，然后回溯。根据访问根节点的顺序不同，深度优先搜索遍历又可细分为前序遍历、中序遍历和后序遍历。

1. 前序遍历（Preorder Traversal）

遍历顺序：根节点 -> 左子树 -> 右子树。即先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。        

2. 中序遍历（Inorder Traversal）

遍历顺序：左子树 -> 根节点 -> 右子树。即先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。

3. 后序遍历（Postorder Traversal）

遍历顺序：左子树 -> 右子树 -> 根节点。即先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。

力扣相关题目：

133. 克隆图

113. 路径总和 II

210. 课程表 II

12.广度优先搜索（BFS）

广度优先搜索遍历也称为层序遍历，它按照树的层次依次访问节点，从根节点开始，逐层向下访问，同一层的节点按照从左到右的顺序访问。

示例问题：

假设有一个二维迷宫，其中 0 表示通路，1 表示墙壁，起点为左上角 (0, 0)，终点为右下角 (m - 1, n - 1)（m 为迷宫的行数，n 为迷宫的列数）。我们需要使用广度优先搜索算法找出从起点到终点的最短路径长度。

import java.util.LinkedList; import java.util.Queue; public class MazeBFS { // 定义四个方向：上、下、左、右 private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public static int shortestPath(int[][] maze) { int m = maze.length; int n = maze[0].length; // 若起点或终点为墙壁，无法到达，返回 -1 if (maze[0][0] == 1 || maze[m - 1][n - 1] == 1) { return -1; } // 用于标记节点是否已访问 boolean[][] visited = new boolean[m][n]; // 创建队列用于 BFS Queue<int[]> queue = new LinkedList<>(); // 将起点加入队列，并标记为已访问 queue.offer(new int[]{0, 0, 0}); visited[0][0] = true; while (!queue.isEmpty()) { int[] current = queue.poll(); int x = current[0]; int y = current[1]; int steps = current[2]; // 若到达终点，返回步数 if (x == m - 1 && y == n - 1) { return steps; } // 尝试四个方向 for (int[] dir : DIRECTIONS) { int newX = x + dir[0]; int newY = y + dir[1]; // 检查新位置是否合法且未访问过，并且是通路 if (newX >= 0 && newX < m && newY >= 0 && newY < n &&!visited[newX][newY] && maze[newX][newY] == 0) { // 标记新位置为已访问 visited[newX][newY] = true; // 将新位置加入队列，并更新步数 queue.offer(new int[]{newX, newY, steps + 1}); } } } // 若无法到达终点，返回 -1 return -1; } public static void main(String[] args) { int[][] maze = { {0, 1, 0, 0}, {0, 0, 0, 1}, {0, 1, 0, 0}, {0, 0, 1, 0} }; int shortest = shortestPath(maze); System.out.println("从起点到终点的最短路径长度为: " + shortest); } }

力扣相关题目：

102. 二叉树的层序遍历

994. 腐烂的橘子

127. 单词接龙