是一种思维逻辑层面的结构，而非程序中的实际存储结构；思维结构可以表示无限的概念
设计问题求解树的状态
在问题求解树搜索过程中，对于某些分支或子树通过某些条件的筛选不进行搜索。
对问题求解树不同的遍历方式
程序实现 =》 递归
层序遍历 =》 队列
适合场景：求解最优化问题
来自Leetcode
下面这个题目即可使用深搜又可使用广搜，理解下两种方法解题
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
示例 1：
输入：root = [1,2,3,4], x = 4, y = 3
输出：false
示例 2：
输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
思路：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int dfs(TreeNode root, int val, TreeNode father) {
if (root == null) return -1;
if (root.val == val) return 0;
father.val = root.val;
int level;
level = dfs(root.left, val, father);
if (level != -1) return level + 1;
father.val = root.val;
level = dfs(root.right, val, father);
if (level != -1) return level + 1;
return -1;
}
public boolean isCousins(TreeNode root, int x, int y) {
int l_x, l_y;
TreeNode father_x = new TreeNode(-1), father_y = new TreeNode(-1);
l_x = dfs(root, x, father_x);
l_y = dfs(root, y, father_y);
return l_x == l_y && father_x.val != father_y.val;
}
}
问题状态： 当前节点 & 父节点 & 当前节点层深
class Solution {
class Node {
TreeNode curr;
TreeNode father;
int level;
public Node(TreeNode curr, TreeNode father, int level) {
this.curr = curr;
this.father = father;
this.level = level;
}
}
public boolean isCousins(TreeNode root, int x, int y) {
int level_x = -1, level_y = -1;
TreeNode father_x = new TreeNode(-1), father_y = new TreeNode(-1);
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(root, null, 0));
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.curr.val == x) {//终止条件：判断是否为带查找元素
level_x = node.level;
father_x = node.father;
}
if (node.curr.val == y) {//终止条件：判断是否为带查找元素
level_y = node.level;
father_y = node.father;
}
if (node.curr.left != null) {//扩展状态【搜索树左右子树】
queue.offer(new Node(node.curr.left, node.curr, node.level + 1));
}
if (node.curr.right != null) {//扩展状态【搜索树左右子树】
queue.offer(new Node(node.curr.right, node.curr, node.level + 1));
}
}
return level_x == level_y && father_x.val != father_y.val;
}
}
给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
路径途经的所有单元格都的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。
示例 1：
输入：grid = [[0,1],[1,0]]
输出：2
示例 2：
输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4
感觉这个题目就是广搜的比较又代表性的题目，其他的题目都是大同小异，可以深入理解下
问题状态：当前元素【一维坐标 & 二维坐标 & 距离起点距离】
class Solution {
int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}};
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid[0][0] != 0) return -1;//当矩阵左上角的第一个元素不为0， 则说明无法开始站在起始位置
int n = grid.length;
int m = grid[0].length;
int[][] visit = new int[n][m];//存储原矩阵相应位置是否被访问过，用于剪枝
visit[0][0] = 1;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0, 1});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
if (curr[0] == n - 1 && curr[1] == n - 1) {//是否满足搜索终止条件 （走到终点）
return curr[2];
}
for (int i = 0; i < dir.length; i++) {//扩展状态【二维矩阵方向数组dir】
int x = curr[0] + dir[i][0];
int y = curr[1] + dir[i][1];
if (x < 0 || x >= n) continue;//剪枝 （下标越界）
if (y < 0 || y >= m) continue;//剪枝 （下标越界）
if (grid[x][y] != 0) continue;//剪枝 （题目要求）
if (visit[x][y] != 0) continue;//剪枝 （重复访问）
visit[x][y] = curr[2] + 1;
queue.offer(new int[]{x, y, visit[x][y]});
}
}
return -1;
}
}
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
分析：
四个边上的O没有被X围绕 =》由这些O向内扩展的所有可达的O均没有被X围绕； 由这些O向内扩展的所有不可达的O均被X围绕
问题状态：当前元素【一维坐标 & 二维坐标 & 是否为O且从四个边的O出发可达】
递归函数设计：
class Solution {
private int n;
private int m;
int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private void dfs(int i, int j, char[][] board) {
board[i][j] = 'o';
for (int k = 0; k < dir.length; k++) {
int x = i + dir[k][0];
int y = j + dir[k][1];
if (x < 0 || x >= n) continue;
if (y < 0 || y >= m) continue;
if (board[x][y] != 'O') continue;
dfs(x, y, board);
}
}
public void solve(char[][] board) {
n = board.length;
m = board[0].length;
for (int i = 0; i < n; i++) {
if (board[i][0] == 'O') dfs(i, 0, board);
if (board[i][m - 1] == 'O') dfs(i, m - 1, board);
}
for (int j = 0; j < m; j++) {
if (board[0][j] == 'O') dfs(0, j, board);
if (board[n - 1][j] == 'O') dfs(n - 1, j, board);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == 'o') {
board[i][j] = 'O';
}
}
}
}
}
还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
分析：题目可以转化为：所拥有的火柴是否可以平均分为四组？
初始化一个大小为4的一维数组(4个桶)，每个元素初始化为火柴总长度/4（桶的容量）;
桶的容量为火柴总长度/4, 当将所有火柴都放入桶中时，代表4个桶均放满
问题状态： 第ind根火柴 & 桶的剩余容量 int[] arr
递归函数：
class Solution {
private boolean dfs(int ind, int[] arr, int[] matchsticks) {
if (ind == -1) return true;//当ind 超限时，说明所有的火柴都放到桶中，且均放满
for (int i = 0; i < arr.length; i++) {//遍历4个桶
if (arr[i] < matchsticks[ind]) continue;//桶的容量不够火柴长度
if (arr[i] == matchsticks[ind] || arr[i] >= matchsticks[ind] + matchsticks[0]) {
arr[i] -= matchsticks[ind];//更新桶的剩余容量
if (dfs(ind - 1, arr, matchsticks)) return true;
arr[i] += matchsticks[ind];//若当前火柴放入当前桶后没有找到解，则需要将火柴从当前桶中拿出
}
}
return false;
}
public boolean makesquare(int[] matchsticks) {
Arrays.sort(matchsticks);
int sum = 0;
for (int matchstick : matchsticks) {
sum += matchstick;
}
if (sum % 4 != 0) return false;
int[] arr = new int[4];
for (int i = 0; i < arr.length; i++) {
arr[i] = sum / 4;
}
return dfs(matchsticks.length - 1, arr, matchsticks);
}
}