深度优先 算法总结

文章目录

[98. 验证二叉搜索树]解题思路 dfs 100 相同的树解题思路 递归 深度优先 [108. 将有序数组转换为二叉搜索树][112. 路径总和](https://leetcode-cn.com/problems/path-sum/)[113. 路径总和 II](https://leetcode-cn.com/problems/path-sum-ii/)**解题思路及注意事项** 200 岛屿的数量**思路****深度优先****广度优先** [257. 二叉树的所有路径][337. 打家劫舍 III][394. 字符串解码]

[98. 验证二叉搜索树]

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1:

输入: 2 / 1 3 输出: true 示例 2:

输入: 5 / 1 4 / 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。

解题思路 dfs

class Solution { long pre = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if(root==null) return true; if(!isValidBST(root.left)){ return false; } //如果当前节点的值比最小值还小 return false if(root.val<=pre){ return false; } //最小的值 pre = root.val; return isValidBST(root.right); } }

100 相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入: 1 1 / \ / 2 3 2 3

[1,2,3], [1,2,3]

输出: true 示例 2:

输入: 1 1 / 2 2

[1,2], [1,null,2]

输出: false 示例 3:

输入: 1 1 / \ / 2 1 1 2

[1,2,1], [1,1,2]

输出: false

解题思路 递归 深度优先

class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if(p==null && q==null){ return true; } if(p==null || q==null ||p.val!=q.val){ return false; } return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); } }

[108. 将有序数组转换为二叉搜索树]

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5 class Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums,0,nums.length-1); } public TreeNode helper(int[] nums,int left,int right){ if(left>right){ return null; } int mid=(left+right)/2; TreeNode root = new TreeNode(nums[mid]); root.left = helper(nums,left,mid-1); root.right = helper(nums,mid+1,right); return root; } }

112. 路径总和

难度简单438收藏分享切换为英文接收动态反馈

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root==null){ return false; } if(root.val==sum && root.left==null && root.right==null){ return true; } return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val); } }

113. 路径总和 II

难度中等356收藏分享切换为英文接收动态反馈

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22，

5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1

返回:

[ [5,4,11,2], [5,8,4,5] ]

解题思路及注意事项

本题的主要思路是深度优先和回溯注意res.add(new ArrayList<>(path)); class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res = new ArrayList<>(); if(root==null){ return res; } Deque<Integer> path = new ArrayDeque<>(); dfs(root,sum,path,res); return res; } private void dfs(TreeNode node,int sum,Deque<Integer> path,List<List<Integer>> res){ if(node==null){ return; } //是叶子节点 if(node.val==sum && node.left==null && node.right == null){ path.addLast(node.val); res.add(new ArrayList<>(path)); path.removeLast(); return; } path.addLast(node.val); dfs(node.left,sum-node.val,path,res); dfs(node.right,sum-node.val,path,res); path.removeLast(); } }

200 岛屿的数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入: [ [‘1’,‘1’,‘1’,‘1’,‘0’], [‘1’,‘1’,‘0’,‘1’,‘0’], [‘1’,‘1’,‘0’,‘0’,‘0’], [‘0’,‘0’,‘0’,‘0’,‘0’] ] 输出: 1 示例 2:

输入: [ [‘1’,‘1’,‘0’,‘0’,‘0’], [‘1’,‘1’,‘0’,‘0’,‘0’], [‘0’,‘0’,‘1’,‘0’,‘0’], [‘0’,‘0’,‘0’,‘1’,‘1’] ] 输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

思路

深度优先

class Solution { private int d[][]={{0,1},{1,0},{0,-1},{-1,0}}; private int n,m; private boolean visited[][]; public int numIslands(char[][] grid){ if(grid==null || grid.length==0 || grid[0].length==0){ return 0; } m = grid.length; n = grid[0].length; visited=new boolean[m][n]; int res = 0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]=='1' && !visited[i][j]){ dfs(grid,i,j); res ++; } } } return res; } private void dfs(char[][] grid,int x,int y){ visited[x][y]=true; for(int i=0;i<4;i++){ int newx = x+d[i][0]; int newy = y+d[i][1]; if(inArea(newx,newy) && !visited[newx][newy] && grid[newx][newy]=='1'){ dfs(grid,newx,newy); } } } //判断访问的地方在合法的区域内 private boolean inArea(int x,int y){ return x>=0 && x<m && y>=0 && y<n; } }

广度优先

class Solution { private int rows; private int cols; public int numIslands(char[][] grid) { int[][] directions={{-1,0},{0,-1},{1,0},{0,1}}; rows = grid.length; if(rows==0){ return 0; } cols = grid[0].length; boolean[][] marked = new boolean[rows][cols]; int count = 0; for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++ ){ if(!marked[i][j]&&grid[i][j]=='1'){ count++; LinkedList<int[]> queue = new LinkedList<>(); queue.addLast(new int[]{i,j}); marked[i][j]=true; while(!queue.isEmpty()){ int[] cur = queue.removeFirst(); for(int k=0;k<4;k++){ int newX =cur[0]+directions[k][0]; int newY =cur[1]+directions[k][1]; if(inArea(newX,newY)&&grid[newX][newY]=='1'&&!marked[newX][newY]){ queue.addLast(new int[]{newX,newY}); marked[newX][newY]=true; } } } } } } return count; } boolean inArea(int x,int y){ return x<rows && x>=0 && y<cols && y>=0; } }

[257. 二叉树的所有路径]

难度简单377收藏分享切换为英文接收动态反馈

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3 class Solution { public List<String> binaryTreePaths(TreeNode root) { ArrayList<String> res = new ArrayList<>(); if(root == null){ return res; } if(root.left==null && root.right==null){ res.add(Integer.toString(root.val)); return res; } List<String> resleft = binaryTreePaths(root.left); for(String s:resleft){ StringBuilder sb =new StringBuilder(Integer.toString(root.val)); sb.append("->"); sb.append(s); res.add(sb.toString()); } List<String> resright = binaryTreePaths(root.right); for(String s:resright){ StringBuilder sb = new StringBuilder(Integer.toString(root.val)); sb.append("->"); sb.append(s); res.add(sb.toString()); } return res; } }

[337. 打家劫舍 III]

难度中等595收藏分享切换为英文接收动态反馈

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1] 3 / \ 4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9. class Solution { public int rob(TreeNode root) { int[] rootSattus = dfs(root); return Math.max(rootSattus[0],rootSattus[1]); } // 可以选择 是否偷这个房子 public int[] dfs(TreeNode node){ if(node == null){ return new int[]{0,0}; } int[] l = dfs(node.left); int[] r = dfs(node.right); int selected = node.val+l[1]+r[1]; int notSelected = Math.max(l[0],l[1])+Math.max(r[0],r[1]); return new int[]{selected,notSelected}; } }

[394. 字符串解码]

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

输入：s = "3[a]2[bc]" 输出："aaabcbc" 输入：s = "3[a2[c]]" 输出："accaccacc" 输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef" 输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz" class Solution { public String decodeString(String s) { StringBuilder res = new StringBuilder(); int multi = 0; LinkedList<Integer> stack_multi = new LinkedList<>(); LinkedList<String> stack_res = new LinkedList<>(); for(Character c:s.toCharArray()){ if(c == '['){ stack_multi.addLast(multi); stack_res.addLast(res.toString()); multi = 0; res = new StringBuilder(); } else if(c==']'){ StringBuilder tmp = new StringBuilder(); int cur_multi = stack_multi.removeLast(); for(int i=0;i<cur_multi;i++) tmp.append(res); res = new StringBuilder(stack_res.removeLast()+tmp); } else if(c>='0'&&c<='9') multi = multi*10+Integer.parseInt(c+""); else res.append(c); } return res.toString(); } }