二叉树总结（一） 1.技巧描述 对于二叉树的问题，一般会采用深度优先搜索和广度优先搜索等方法来解决。 深度优先搜索：深度优先搜索会沿着某一条路一直往前走，直到走完这条路为止，有点类似不撞南墙不回头，一般使用递归来实现。 广度优先搜索：广度优先搜索会考虑所有可能的路径，每次往前走一步，都相当于在上一步的基础上进行扩展，一般采用队列的方式来实现。 2.实战演练 二叉树根节点到叶子节点的所有路径和 本题使用了深度优先搜索的方法。并通过回溯的方式，让路径回退到上一个节点，达到重置原路径的目的。 二叉树中的最大路径和 本题使用了深度优先搜索的方法。并通过定义贡献值的方式来找所有可能的...

题意整理 给定一个用n*m矩阵表示的群岛的地图，其中1表示岛屿，0表示海洋。 求最大的岛屿的面积，两个岛屿相邻算同一个岛屿。 方法一（深度优先搜索） 1.思路整理 遍历所有的岛屿。 如果当前岛屿面积为1，则通过深度优先搜索（利用递归实现），找到与之相邻的所有的岛屿，计算其面积。 统计所有面积中的最大者，作为岛屿的最大面积。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param ...

题意整理 给定一个链表，要求两两交换相邻节点。 方法一（递归） 1.思路整理 递归终止条件：只有一个节点，或没有节点了，递归终止。 递归如何传递：通过递归可以得到从当前节点的下下个节点断开之后的链表。比如1-2-3-4中的3-4部分。然后将当前节点的下一个节点，指向这个断开之后的链表，同时记录当前节点的下一个节点作为当前层的头节点newHead，并将head指向断开之后的链表，newHead指向head。 递归的返回值：返回当前层头节点newHead。 2.代码实现 import java.util.*; /* * public class ListNode { * int ...

题意整理 给定两个用字符串表示的二进制数。 求它们的和，同样以字符串形式返回。 方法一（模拟竖式计算） 1.思路整理 模拟这两个数竖式计算的过程。 逐次从低位到高位相加，逢二进一，每次将当前位加入到结果，同时记录余数。 最后将结果反转之后返回。 图解展示： 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A string字符串 * @param B stri...

题意整理 给定一个字符串s，长度为n，求s的所有子序列。 如果子序列重复，则只添加一次。 方法一（回溯） 1.思路整理 首先将字符串转化为字符数组。 然后对字符数组进行遍历，每一个字符要么添加、要么不添加，利用回溯法添加字符数组中所有可能的字符组合，每一个组合代表一个子序列。每完成一轮添加，将对应组合加入到结果集。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s st...

题意整理 给定一颗二叉树的根节点root。 求该二叉树的前序遍历。 方法一（递归） 1.思路整理 先序遍历的顺序是根、左、右。如果直接按照递归的思路进行遍历，只需在对应的位置将当前节点加入到序列即可。 2.代码实现 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * }...

题意整理 给定一颗二叉树。 判断该树是否是二叉搜索树。 方法一（递归） 1.思路整理 判断搜索二叉树（BST）： 考虑搜索二叉树的定义，每一个节点的值应该大于等于左子树中的最大值，小于等于右子树中的最小值。所以我们可以利用递归遍历每一个节点，如果某个节点不满足定义，则不合法，直接返回false。 图解展示： 2.代码实现 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public...

题意整理 给定两个整数数组，求两个数组的最长的公共子数组的长度。 方法一（动态规划） 1.解题思路 状态定义：dp[i][j]表示A的子数组以i-1结尾，B的子数组以j-1结尾时的最长公共子数组长度。 状态转移：两层循环，遍历A数组和B数组中每一个元素，如果当前元素相等，则由左上方对应位置状态加1，即dp[i][j]=dp[i−1][j−1]+1dp[i][j]=dp[i-1][j-1]+1dp[i][j]=dp[i−1][j−1]+1，否则重置为0。每次取所有可能的最大值。 2.代码实现 import java.util.*; public class Solution { ...

题意整理 给定一个用数组表示的数字，即数组中每个数表示一个数位上的数，例如[1,2,3][1,2,3][1,2,3]，表示123。 求这个数字加1后的结果，以数组的形式返回。 方法一（模拟） 1.解题思路 首先定义一个长度为n+1的新数组res和一个进位carry。 然后逆序遍历原数组，根据进位，模拟数组加1的过程。 如果最后进位为0，说明数组长度不变，只需返回res最后n位。如果进位位1，则需要给索引位0的位置赋值，并返回新数组。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名...

题意整理 给定一个由小写字母组成的长度为n的字符串S，找出所有长度为k且包含重复字符的子串。 返回全部满足要求的子串的数目。 方法一（字符串截取） 1.解题思路 遍历整个字符串，依次截取长度为k的子串。 每次判断子串是否包含重复字符，如果包含，则计数加1。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param k int整型...

题意整理 给定一个二叉树结构的小区，每个节点都有一个房子。 现在有一个小偷，想偷到尽可能多的现金，但是不能偷相邻的房间，问最多偷多少现金。 方法一（递归） 1.解题思路 递归终止条件：遍历完所有节点。 递归如何传递：分别计算选与不选当前节点的情况。如果选，则加上当前节点、左孩子对应的孙子的情况，右孩子对应的孙子的情况。如果不选，则加上左孩子的最大值、右孩子的最大值。 递归的返回值：返回当前节点的最大情况。 这种方法运行会超时。 2.代码实现 import java.util.*; /* * public class TreeNode { * int val = 0; * ...

题意整理 给定n个房子排成一圈，每个房子都有一定现金。 现在有一个小偷，想偷到尽可能多的现金，但是不能偷相邻的房间，问最多偷多少现金。 方法一（动态规划） 1.解题思路 状态定义：dp[i]dp[i]dp[i]表示到第i个房间为止，能偷到的最多的现金。 状态初始化：到第0个房间时，最多偷第0个房间的现金。到第1个房间时，最多偷第0个房间或第1个房间的现金，两者中取较大者。 状态转移：要么是前前家+当前，要么是前一家，取较大者。即dp[i]=Math.max(dp[i−1],dp[i−2]+nums[i])dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i])dp[...

题意整理 给定并排的n个房子，每个房子都有一定现金。 现在有一个小偷，想偷到尽可能多的现金，但是不能偷相邻的房间，问最多偷多少现金。 方法一（动态规划） 1.解题思路 状态定义：dp[i]dp[i]dp[i]表示到第i个房间为止，能偷到的最多的现金。 状态初始化：到第0个房间时，最多偷第0个房间的现金。到第1个房间时，最多偷第0个房间或第1个房间的现金，两者中取较大者。 状态转移：要么是前前家+当前，要么是前一家，取较大者。即dp[i]=Math.max(dp[i−1],dp[i−2]+nums[i])dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i])dp[i...