珠海公司网站制作公,汕尾建设网站,wordpress商家插件,贵州省建设银行招聘网站目录
4.1 二叉树的最大深度#xff08;简单#xff09;#xff1a;深度优先搜索
4.2 对称二叉树#xff08;简单#xff09;#xff1a;递归
4.3 岛屿数量#xff08;中等#xff09;#xff1a;深度优先搜索
4.4 岛屿的最大面积#xff08;中等#xff09;简单深度优先搜索
4.2 对称二叉树简单递归
4.3 岛屿数量中等深度优先搜索
4.4 岛屿的最大面积中等深度优先搜索
4.5 路径总和简单深度优先搜索
4.6 被围绕的区域中等深度优先搜索
4.7 路径总和Ⅱ中等深度优先搜索
4.8 树的子结构中等前序遍历 递归
4.9 合并二叉树简单深度优先搜索
4.10 二叉搜索树的最近公共祖先中等两次遍历
4.11 所有可能的路径中等深度优先搜索 递归
4.12 省份数量中等深度优先搜索
4.13 深度优先搜索的总结 4.1 二叉树的最大深度简单深度优先搜索
题目给定一个二叉树 root 返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
思想对于树而言可以使用递归的方式来计算根节点的左右子节点的最大深度因此二叉树的最大深度应该等于 左右子节点最大深度 1 总结元素对应的最小路径和与其相邻元素的最小路径和有关因此可以采用动态规划具体是 元素对应的最小路径和 min(上方相邻元素对应的最小路径和左方相邻元素对应的最小路径和) 当前元素值 设dp[i][j]表示从左上角出发到[i][j]的最小路径和有dp[i][j] min(dp[i-1][j],dp[i][j-1]) grid[i][j] 特殊情况 只有一个点dp[0][0] grid[0][0]第一个数的最小路径和为该数的值 只有一行i0,dp[0][j] dp[0][j-1] grid[0][j] 只有一列j0,dp[i][0] dp[i-1][0] grid[i][0] 代码
class Solution {public int maxDepth(TreeNode root) {//根节点为nullif(root null){return 0;}//只有根节点if(root.left null root.right null){return 1;}//根节点存在左右子树则比较左右子树的最大深度取其较大值 1int max_Depth 0;//得到左子树的最大深度if(root.left ! null){max_Depth Math.max(maxDepth(root.left),max_Depth);}//得到右子树的最大深度if(root.right ! null){max_Depth Math.max(maxDepth(root.right),max_Depth);}
return max_Depth 1;
}
} 4.2 对称二叉树简单递归
题目给你一个二叉树的根节点 root 检查它是否轴对称
思想可以先实现一个递归函数使用两个指针p和q同步遍历树两个指针开始时都指向根节点随后p右移时q左移p左移时q右移检查当前指针值是否相等 总结判断二叉树是否对称只需看 根节点是否一致 左右子树是否值相等且对称 可将一个root作两个用然后分别比较root的左右子树值是否都相等 代码
class Solution {public boolean isSymmetric(TreeNode root) {return check(root, root);}
public boolean check(TreeNode p, TreeNode q) {//先判断是否为空if (p null q null) {return true;}//比较根节点是否相等if (p null || q null) {return false;}//比较根节点值是否都相同然后比较p的左子树与q的右子树是否相等并比较p的右子树与q的左子树是否相等return p.val q.val check(p.left, q.right) check(p.right, q.left);}
} 4.3 岛屿数量中等深度优先搜索
题目给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。
思想其实这是一个寻找连通块数量的问题岛屿只能从1开始然后寻找与它相连接上下左右的1的数量每一次找寻完毕后就说明这个连通块是一个岛屿然后将找过的连通块中的元素由1设置为0同一个岛屿在下一次找寻时是不会在此搜索的 总结深度优先搜索会从当前值开始沿着某个节点一直走下去直到结束然后进行其它方向的搜索直到搜索完相邻节点我们只需给出搜索的起点与搜索方法即可 注意边界条件对于数组而言不能超出左右边界[0, maxLength]; 代码
class Solution {public int numIslands(char[][] grid) {//grid为空直接返回0if(grid null || grid.length 0){return 0;}
//找到grid的行与列为DFS做准备 int row grid.length;int column grid[0].length;
//设置常量记录连通块岛屿数量int num_Islands 0;
//进行DFS查找for(int i 0; i row; i){for(int j 0; j column; j){//岛屿的前提条件是值为1if(grid[i][j] 1){num_Islands;dfs(grid, i, j);}}}return num_Islands;}
private void dfs(char[][] grid, int i, int j){//如果i、j超过边界(两种情况要么小于0要么大于数组长度)、数组值为0则直接返回if(i 0 || j 0 || i grid.length || j grid[0].length || grid[i][j] 0){return;}
//将搜索过的数组值设置为0下一次搜索就不会在搜索到grid[i][j] 0;
//进行深度优先搜索: 上下左右都搜索一遍dfs(grid, i - 1, j);dfs(grid, i 1, j);dfs(grid, i, j - 1);dfs(grid, i, j 1);}
} 4.4 岛屿的最大面积中等深度优先搜索
题目给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0代表水包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿则返回面积为 0 。
思想也是一个寻找连通块数量的问题只不过找到每个连通块还需要计算寻找连通块走过的步数为了不重复走同一个位置将找过的连通块中的元素由1设置为0同一个岛屿在下一次找寻时是不会在此搜索的 总结深度优先搜索会从当前值开始沿着某个节点一直走下去直到结束然后进行其它方向的搜索直到搜索完相邻节点我们只需给出搜索的起点与搜索方法即可 注意边界条件对于数组而言不能超出左右边界[0, maxLength]; 代码
class Solution {public int maxAreaOfIsland(int[][] grid) {if(grid null || grid.length 0 || grid[0].length 0){return 0;}int row grid.length;int column grid[0].length;int res 0;for(int i 0; i row; i){for(int j 0; j column; j){res Math.max(res, dfs(grid, i, j));}}return res;}
private int dfs(int[][] grid, int curr_i, int curr_j){if(curr_i 0 || curr_j 0 || curr_i grid.length || curr_j grid[0].length || grid[curr_i][curr_j] 0){return 0;}grid[curr_i][curr_j] 0;
//为了方便求出DFS走过多少步将上下左右操作需要 - 的两写入矩阵int[] di {0,0,1,-1};int[] dj {1,-1,0,0};
int res 1;//一样进行遍历; 分上下左右的4次遍历即可for(int i 0; i 4; i){int curr_i1 curr_i di[i];int curr_j1 curr_j dj[i];res dfs(grid, curr_i1, curr_j1);}return res;}
} 4.5 路径总和简单深度优先搜索
题目给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false
思想按照深度优先搜索的思想从根节点开始一条路走到叶子节点并计算路径和可以换一种思路一条路走下去判断目标值 targetSum 和走过的节点之差到达叶子节点时 targetSum currNode.val sum减到最后的值等于该叶子节点的值说明是一条符合路径 总结深度优先搜索就是一条路走到黑不行再从最近路径换一条继续走到黑 本题的巧妙之处在于targetSum - root.val将原本的求和转换思考为求目标值与每次路径差 代码
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {//根节点为空直接返回falseif(root null){return false;}
//如果没有左右子树说明是根节点也是叶子节点判断值是否相等即可if(root.left null root.right null){return root.val targetSum;}
//如果存在左右子树进行深度优先搜索;//注意这条可行路径可能是左子树也可能是右子树减到叶子节点时如果该叶子节点值等于sum就说明是符合要求的路径return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}
} 4.6 被围绕的区域中等深度优先搜索
题目给你一个 m x n 的矩阵 board 由若干字符 X 和 O 找到所有被 X 围绕的区域并将这些区域里所有的 O 用 X 填充
注意任何边界上的 O 都不会被填充为 X因此所有的不被包围的 O 都直接或间接与边界上的 O 相连。我们可以利用这个性质判断 O 是否在边界上
思想以每一个边界上的O为起点标记与它直接或间接相连的字母O 最后我们遍历这个矩阵对于每一个字母 如果该字母被标记过则该字母为没有被字母 X 包围的字母 O我们将其还原为字母 O 如果该字母没有被标记过则该字母为被字母 X 包围的字母 O我们将其修改为字母 X。 总结深度优先搜索就是一条路走到黑不行再从最近路径换一条继续走到黑 本题的巧妙之处在于targetSum - root.val将原本的求和转换思考为求目标值与每次路径差 代码
class Solution {public void solve(char[][] board) {//如果数组为空、只有一个值则不进行区域填充if(board null || board.length 0 || board[0].length 0){return;}
//对 m * n 的左右边界进行DFS搜索for(int i 0; i board.length; i){dfs(board, i, 0);dfs(board, i, board[0].length - 1);}//对 m * n 的上下边界进行DFS搜索排除左右搜索过的节点for(int j 1; j board[0].length - 1; j){dfs(board, 0, j);dfs(board, board.length - 1, j);}
//对所有节点判断若被标记过isO的就是连着边界O的无法被填充为X;将其他节点均填充为X即可for(int i 0; i board.length; i){for(int j 0; j board[0].length; j){if(board[i][j] A){board[i][j] O;}else{board[i][j] X;}}}
}
private void dfs(char[][] board,int row, int column){//边界条件且只对边界上的O进行DFS搜索if(row 0 || row board.length || column 0 || column board[0].length || board[row][column] ! O){return;}//对于dfs的这个O点做一个标记设为isOboard[row][column] A;
//进行上下左右dfs搜索dfs(board, row, column - 1);dfs(board, row, column 1);dfs(board, row - 1, column);dfs(board, row 1, column);}
} 4.7 路径总和Ⅱ中等深度优先搜索
题目给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
思想按照深度优先搜索的思想从根节点开始一条路走到叶子节点并计算路径和可以换一种思路一条路走下去判断目标值 targetSum 和走过的节点之差到达叶子节点时 targetSum currNode.val sum减到最后的值等于该叶子节点的值说明是一条符合路径 总结深度优先搜索就是一条路走到黑不行再从最近路径换一条继续走到黑 本题的巧妙之处在于targetSum - root.val将原本的求和转换思考为求目标值与每次路径差 代码
class Solution {public ListListInteger pathSum(TreeNode root, int targetSum) {//创建一个存储结果的数组ListListInteger res new ArrayList();//创建一个双端队列存储每次符合目标的路径//注意之所以用双端队列是因为比如一条路径走到叶子节点了先加左节点不等于sum此时可以在尾部删除添加的左节点然后再在尾部加上右节点的值DequeInteger deque new LinkedList();dfs(root, targetSum, res, deque);return res;}
private void dfs(TreeNode root, int targetSum, ListListInteger res, DequeInteger deque){if(root null){return;}//将节点值加入双端队列deque.offerLast(root.val);//目标值减少targetSum - root.val;
//如果到了叶子节点且targetSum 0;说明是符合条件的路径将deque加入resif(root.left null root.right null targetSum 0){res.add(new LinkedList(deque));}
//搜索左子树与右子树节点dfs(root.left, targetSum, res, deque);dfs(root.right, targetSum, res, deque);
//如果最后一个节点不符合要求将最后一个节点删除deque.pollLast();
}
} 4.8 树的子结构中等前序遍历 递归
题目输入两棵二叉树A和B判断B是不是A的子结构。(约定空树不是任意一个树的子结构);B是A的子结构 即 A中有出现和B相同的结构和节点值。
思想一棵树B是另一棵树A的子树的前提是 A不能为空 B为空则B一定是A的子树 B不为空则存在三种可能 B是A从根节点下出发的子结构 此时要判断B和A的根节点值是否相同不同就肯定不是 如果B和A的根节点值相同则继续判断B和A的左右子树是否相同 B是A的左子树中的子结构 B是A的右子树中的子结构 总结本题的重点在于递归判断B是否为A的根节点下出发的子结构进而判断B 的左右子树节点是否为A的左右子树节点 代码
class Solution {public boolean isSubStructure(TreeNode A, TreeNode B) {//B是A的子节点在同时不为空三种情况B是A的根节点出发的子结构、B是A左子树子结构、B是A右子树子结构return (A ! null B ! null) (isSubRoot(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B));}
private boolean isSubRoot(TreeNode A, TreeNode B){//B为空则就是子结构if(B null){return true;}
//A为空或者A、B的根节点值不同则返回falseif(A null || A.val ! B.val){return false;}
//到这一步说明A、B的根节点值相同则判断A、B的左右子节点是否相同//此时需要递归因为A、B的左右子节点判断时一样是在证明B的左右子节点是否是A的左右子节点出发的子结构其实就是下面的情况B是A的根节点出发的子结构因此调用isSubRoot()即可return isSubRoot(A.left, B.left) isSubRoot(A.right, B.right);}
} 4.9 合并二叉树简单深度优先搜索
题目给你两棵二叉树 root1 和 root2 。
想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。注意: 合并过程必须从两个树的根节点开始。
思想深度优先搜索合并合并对应节点有三种情况 两个节点都为空合并后对应节点位置为空 只有一个节点为空合并后对应节点位置是不为空节点的值 两个节点都不为空合并后对应节点位置为两个值相加 总结广度优先搜索的步骤 从某个节点开始搜索将该节点存入队列 若队列不为空进行循环该节点出队 根据路径访问该节点的相邻节点加入队列中直到所有节点被访问 代码
class Solution {//合并两棵树public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {//如果任意一棵树为空直接返回另一棵树即可if(root1 null){return root2;}if(root2 null){return root1;}//创建一颗新树根节点为根节点之和TreeNode newTree new TreeNode(root1.val root2.val);//合并两个树的左节点newTree.left mergeTrees(root1.left,root2.left);
//合并两个树的右节点newTree.right mergeTrees(root1.right, root2.right);
return newTree;}
} 4.10 二叉搜索树的最近公共祖先中等两次遍历
题目给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先和1.11题解可以一样但是二叉搜索树具有特定性质可以根据其性质进行求解 最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
思想二叉搜索树的特点在于有序节点的左子树都比该节点小节点的右子树都比该节点大使用二次遍历法对于节点p而言 从根节点遍历 如果当前节点为p则找到节点 如果当前节点值大于p则 p在当前节点的左子树 如果当前节点值小于p则p在当前节点的右子树 寻找节点的同时记录走过的节点当找到p与q的路径pathP[i]和pathQ[i]后p和q路径上的最后一个相同点就是最近公共祖先即pathP[i] pathQ[i]时只要i最大即可 总结首先需要读懂题意然后才能入手解决这种较为复杂的问题可以设置一个专门判断是否存在节点p、q的函数从而根据两种情况递归的使用该函数最终得到结果 代码
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//拿到从根节点找到p或者q的路径ListTreeNode pathP getPath(root, p); ListTreeNode pathQ getPath(root, q);TreeNode ancestor new TreeNode();//找到路径后拿到两数组相等时的最大节点就是最近公共祖先for(int i 0; i pathP.size() i pathQ.size(); i){if(pathP.get(i) pathQ.get(i)){ancestor pathP.get(i);}}return ancestor;}
private ListTreeNode getPath(TreeNode root, TreeNode p){//创建接收走过路径的数组ListTreeNode res new ArrayList();TreeNode node root;
//如果root值不等于p的值根据p与root的左右节点的大小判断p在左子树还是右子树while(node.val ! p.val){res.add(node);if(p.val node.val){node node.left;}else{node node.right;}}//如果root值等于p的值也要放进数组表示从根节点找到了pres.add(node);return res;}
} 4.11 所有可能的路径中等深度优先搜索 递归
题目给你一个有 n 个节点的 有向无环图DAG请你找出所有从节点 0 到节点 n-1 的路径并输出不要求按特定顺序
graph[i] 是一个从节点 i 可以访问的所有节点的列表即从节点 i 到节点 graph[i][j]存在一条有向边。
思想使用深度优先搜索求出可能路径从0出发使用栈记录路径上的点每次遍历到n - 1就将栈中的记录加入答案中 有向无环图说明不会遍历同一个点因此无法判断是否遍历过 总结首先需要读懂题意然后才能入手解决这种较为复杂的问题可以设置一个专门判断是否存在节点p、q的函数从而根据两种情况递归的使用该函数最终得到结果 代码
class Solution {//设置一个二维集合用来记录所有路径ListListInteger res new ArrayList();//设置一个栈用来辅助深度优先搜索栈的实现不再用stack而是用deque代替栈的作用就是从一个节点的路径出发如果一条路走到黑可以方便的回到上一个节点继续向另一条路出发因为栈是先入后出的可以保证前面的路径正确只是最后一条路走到了头最后将走到头的栈的值存入二维集合中即可DequeInteger stack new LinkedList();
public ListListInteger allPathsSourceTarget(int[][] graph) {//从节点0出发因此栈中第一个元素是节点0stack.offerLast(0);//搜索从节点0到节点n - 1的路径dfs(graph, 0, graph.length - 1);return res;}
private void dfs(int[][] graph, int x, int n){//如果搜索到n - 1节点则将其加入集合中(注意此时的n就是graph.length - 1即n - 1)if(x n){res.add(new ArrayListInteger(stack));return;}
//如果还没搜索到最后一个节点则从节点0所在索引的所有值出发搜索for(int y : graph[x]){stack.offerLast(y);//从节点0索引的每一个值出发搜索路径即可dfs(graph, y, n);//每次搜索完毕后出栈stack.pollLast();}}
} 4.12 省份数量中等深度优先搜索
题目有 n 个城市其中一些彼此相连另一些没有相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected 其中 isConnected[i][j] 1 表示第 i 个城市和第 j 个城市直接相连而 isConnected[i][j] 0 表示二者不直接相连。返回矩阵中 省份 的数量。
思想其实就是求一个矩阵中的连通块数量使用深度优先搜索 遍历所有城市如果城市未被访问过则从该城市开始深度优先搜索 通过 isConnected 可以知道该城市与哪个城市相连 相连城市就是一个连通分量直到同一个连通分量的所有城市都被访问到就能够得到一个省份 最终所有连通分量的总数就是省份总数 总结广度优先搜索的步骤 从某个节点开始搜索将该节点存入队列 若队列不为空进行循环该节点出队 根据路径访问该节点的相邻节点加入队列中直到所有节点被访问 代码
class Solution {public int findCircleNum(int[][] isConnected) {//城市数量int city isConnected.length;//设置省份数量int province 0;boolean[] isVisited new boolean[city];//遍历所有城市如果城市未被访问过则进行深度优先搜索 for(int i 0; i city; i){if(isVisited[i] false){dfs(isConnected, city, i, isVisited);province;}}return province;}
//从当前节点对所有城市进行深度优先搜索路径按照isConnected中给出访问过后将状态修改为true默认为falseprivate void dfs(int[][] isConnected, int city, int i, boolean[] isVisited){for(int j 0; j city; j){if(isConnected[i][j] 1 isVisited[j] false){isVisited[j] true;//当前节点搜索后从相邻节点继续搜索dfs(isConnected, city, j, isVisited);}}}
} 4.13 深度优先搜索的总结 思想深度优先搜索就是一条路走到黑从某个节点出发然后一直走到头然后从上一个节点继续出发走到头直到所有节点都搜索完毕 实现实现深度优先搜索时应注意三点 观察节点出发的路径如何实现在数组中经常是上下左右的实现比如 //进行深度优先搜索: 上下左右都搜索一遍dfs(grid, i - 1, j);dfs(grid, i 1, j);dfs(grid, i, j - 1);dfs(grid, i, j 1);
//或者利用循环for(int j 0; j city; j){if(isConnected[i][j] 1 isVisited[j] false){isVisited[j] true;//当前节点搜索后从相邻节点继续搜索dfs(isConnected, city, j, isVisited);}} 节点访问过后的标记通常是使用boolean[] flag标记即可访问后设置为true 访问过的节点路径的存储特殊情况下要用到栈
