题意整理  给定两个字符串s1和s2。 求这两个字符串的最长公共子序列的长度。  方法一（动态规划） 1.解题思路  状态定义：dp[i][j]dp[i][j]dp[i][j]表示s1长度为i，s2长度为j时的最长公共子序列的长度。 状态初始化：初始阿长度均为0。 状态转移：两层循环遍历s1和s2中每一个字符。若当前字符相等，则由之前的最长公共子序列加1。即dp[i+1][j+1]=dp[i][j]+1dp[i+1][j+1]=dp[i][j]+1dp[i+1][j+1]=dp[i][j]+1。否则，取dp[i][j+1]、dp[i+1][j]两者中较大值。即dp[i+1][j+1]=Math...

题意整理  给定一个长度为n的数组。 求它的最长上升子序列的长度。子序列是指按原来数组顺序取的若干个数字组成的序列，上升子序列是指序列中元素严格单调递增。  方法一（动态规划） 1.解题思路  状态定义：dp[i]dp[i]dp[i]表示以下标i结尾的最长上升子序列的长度。 状态初始化：以任意下标结尾的上升子序列长度不小于1，故初始化为1。 状态转移：遍历数组中所有的数，再遍历当前数之前的所有数，只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变，取两者中的较大者。即dp[i]=Math.max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+...

题意整理  给定一个长度为n的数组。 求它的最长上升子序列的长度。子序列是指按原来数组顺序取的若干个数字组成的序列，上升子序列是指序列中元素严格单调递增。  方法一（动态规划） 1.解题思路  状态定义：dp[i]dp[i]dp[i]表示以下标i结尾的最长上升子序列的长度。 状态初始化：以任意下标结尾的上升子序列长度不小于1，故初始化为1。 状态转移：遍历数组中所有的数，再遍历当前数之前的所有数，只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变，取两者中的较大者。即dp[i]=Math.max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+...

1.技巧描述 对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如预处理、用迭代代替递归、回溯。   预处理：比如对要处理的数据提前做哈希映射，或者计算前缀和、后缀和，计算差分数组，构建前缀树，构建树状数组等等。   用迭代代替递归：递归一般会有很多重复的计算过程，可以用迭代代替递归，从而提高效率。一般使用栈的方式来实现。   回溯：通过特定的方式，回到上一层递归的状态。一般是删除集合最后一个元素，或者重置到原来的长度等等。   2.实战演练  合并二叉树  本题使用了深度优先搜索的方法。对合并节点进行处理时，如果两者都不为空，新建一个节点，值为t1的值...

1.技巧描述 对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如建立辅助函数、用迭代代替递归、分情况讨论、预置标记变量。   建立辅助函数：有时候一个大问题不好解决，但是先解决掉其中一个关键问题，后续就比较好办了。比如要判断A树中是否包含与B树完全相同的子树，可以先建立辅助函数，判断两棵子树是否完全相同，然后再遍历A树中所有的子树，依次进行判断即可。   用迭代代替递归：递归一般会有很多重复的计算过程，可以用迭代代替递归，从而提高效率。一般使用栈的方式来实现。   分情况讨论：一个复杂的问题可以拆分成多种情况来解决。比如求最近公共祖先。可以分四种情况，...

1.技巧描述 对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如剪枝、预处理、回溯。   剪枝：提前排除掉不合法的情况。   预处理：比如对要处理的数据提前做哈希映射，或者计算前缀和、后缀和等等。具体情况具体分析。   回溯：通过特定的方式，回到上一层递归的状态。一般是删除集合最后一个元素，或者重置到原来的长度等等。   2.实战演练  判断是不是平衡二叉树  本题使用了剪枝的技巧。如果当前子树深度为-1，则直接作为不合法的情况排除掉。  二叉树中和为某一值的路径(二)  本题使用了回溯的技巧。通过移除集合最后一个元素，回溯到上一层节点。  重建二叉树...

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

方法一（深度优先搜索） 1.题意整理  给定一颗二叉树以及一个整数sum，二叉树中每个节点对应一个节点值。 找出二叉树中所有的从根节点到叶子节点的节点值之和等于sum的路径。  2.思路整理 可以利用深度优先搜索，遍历所有可能的路径，然后看某个路径的和是否等于sum，如果存在这样的路径，则加入到结果集。  递归终止条件：当搜索完所有路径，即root为空，还没有找到合法路径，直接返回false。 递归如何传递：每次需要往左右子树方向递归，sum的值要减去当前节点值，如果遇到叶子节点，并且sum为0，说明路径合法，将当前路径直接加入到结果集。  图解展示：  3.代码实现 import java....

方法一（递归） 1.题意整理  给定一颗二叉树。 求该二叉树的镜像。  2.思路整理  递归结束条件：当前节点为空。 递归如何传递：每次需要交换当前节点的左子节点和右子节点，然后依次往左子树方向递归、往右子树方向递归。 递归的返回值：每次返回当前节点。  图解展示：  3.代码实现 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val...

方法一（栈） 1.题意整理  给定一颗二叉树。 按照中序打印二叉树中所有的节点。  2.思路整理 简单分析：先序遍历的顺序是根、左、右，中序遍历的顺序是左、根、右，后序遍历的顺序是左、右、根。如果直接按照递归的思路进行遍历，只需在对应的位置将当前节点加入到序列即可。 比如中序遍历：  List<Integer> in=new ArrayList<Integer>(); private void inorder(TreeNode root){ if(root==null) return; //往左子树方向遍历 inorder(root.left); //加入到序列 in....

方法一（递归+BFS） 1.题意整理  给定一颗二叉树的前序遍历序列和中序遍历序列。 打印出二叉树的右视图。  2.思路整理 重建二叉树： 一个朴素的思路是，先找到前序序列的第一个元素，将其作为头节点，然后通过遍历中序序列，找到中序序列对应的头节点位置，则中序序列中该位置之前的一定是当前节点的左子树部分，该位置之后的一定是当前节点的右子树部分。知道了左右子树的节点个数，我们便可以推导出前序序列中左右子树的分界点。这样我们便可以构建当前节点的左右子树，通过递归的方式，便可以构建出树中每一个节点。 上面的思路中是通过遍历中序序列找到对应当前节点的位置，由于每次递归都需要搜索整个中序序列，时间复杂度...

方法一（递归） 1.题意整理  给定两颗二叉树，将它们合并为一颗二叉树。 合并规则是：都存在的节点，就将节点值加起来，否则空的位置就由另一颗树的节点来代替。  2.思路整理 只需利用递归确定合并之后的树的每一个节点值。如果其中一棵树的当前节点为空，直接返回另一颗树的节点。如果均不为空，则将当前的两个节点值相加，并据此新建一个节点，然后递归地确定左子节点和右子节点。  递归终止条件：t1为空，返回t2。t2为空，返回t1。 递归如何推进：确定好合并二叉树的当前节点之后，要想确定当前节点左子节点，只需往两棵树左子树方向递归。同理，确定右子节点，需要往右子树方向递归。 递归的返回值：返回合并二叉树的...

方法一（递归） 1.题意整理  给定一颗二叉树，以及这个二叉树上两个节点对应的值o1和o2。 找到该树中o1、o2节点最近的公共祖先。  2.思路整理 可以试图遍历整颗二叉树，判断以当前节点为根的子树的左右子树上是否包含o1和o2，如果左右子树一边一个，则当前节点就是公共祖先。如果全在左子树，则左子树根节点为公共祖先。如果全在右子树，则右子树根节点为公共祖先。如果都没找到，返回-1。  递归终止条件：所有子树遍历之后，都没有找到，直接返回-1。 递归如何推进：需要判断当前节点左右子树是否找到了对应节点，如果均不为-1，说明各找到一个，返回当前节点。如果全在左子树，返回left，如果全在右子树，...

方法一（递归+广度优先搜索） 1.题意整理  给定一颗二叉树，树中没有重复节点。 判断该树是否是二叉搜索树、是否是完全二叉树。  2.思路整理 判断搜索二叉树（BST）： 考虑搜索二叉树的定义，每一个节点的值应该大于等于左子树中的最大值，小于等于右子树中的最小值。所以我们可以利用递归遍历每一个节点，如果某个节点不满足定义，则不合法，直接返回false。 图解展示：  判断完全二叉树（CST）： 完全二叉树是严格按照顺序从上到小，从左到右排列的二叉树，只有上一层满了，才可以在下一层从左到右开始排。所以可以利用层序遍历模拟这个过程，如果遍历的过程中，发现之前出现过空节点，而当前节点不是叶子节点，则...