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

方法一（BFS） 1.题意整理 实现两个函数，分别用来序列化和反序列化二叉树。 序列化是指将二叉树按照某种遍历方式保存为字符串。 反序列化是指根据序列化之后的字符串，重建二叉树。 2.思路整理 序列化：按照广度优先遍历的思路，首先将根节点入队，然后每次弹出当前节点，如果为空，说明不存在左右子节点，直接将"null"（用来表示空节点）加入到结果中，并加一个","用来间隔每一个节点。如果不为空，除了将当前节点值加","加入到结果中，还要将左右子节点入队。 图解展示： 反序列化：相当于序列化的逆操作，首先根据","将字符串分割为字符串数组，根据字符串数组第一个元素新建根节点，并将根节点入队。每...

方法一（BFS） 1.题意整理 给定一颗二叉树。 求二叉树的之字形遍历。之字形遍历是指第一层从左到右，第二层从右到左，一直这样交替。 2.思路整理 这题和二叉树的层序遍历非常相似，可以利用广度优先搜索来做。唯一不同的是，遇到偶数层的时候，需要对该层所有元素进行反转操作，然后再加入到结果集中。 首先新建一个队列，将根节点入队。 只要队列不为空，说明还可以继续遍历。当前队列大小即为当前层中节点个数。 每次遍历当前层所有节点，加入到临时list。遍历完之后加入到结果集。如果是偶数层，反转之后再加入到结果集。如果当前层节点的左右子节点不为空，则可以作为下一层节点加入到队列。 图解展示： 3....

方法一（递归） 1.题意整理 给定一颗二叉树。 判断其是否是自己的镜像。 2.思路整理 首先考虑二叉树是否为空，如果为空，则说明是对称的，直接返回true。否则递归地判断左右子树是否是对称的。 递归终止条件：如果左右子树同时为空，说明所有子树都满足要求，返回true。如果左子树为空，右子树不为空或者右子树为空，左子树不为空，说明不满足对称要求，返回false。 递归如何传递：每次递归，都要比较当前节点root1和root2相等，同时比较root1左子节点是否等于root2右子节点，root1右子节点是否等于root2左子节点。 递归的返回值：返回当前层节点是否符合对称的要求。 图解展示...

方法一（递归+哈希表） 1.题意整理 给定一颗二叉树的前序遍历序列和中序遍历序列。 重建该二叉树，并返回头节点。 2.思路整理 因为前序遍历是按根、左、右的顺序访问节点，中序遍历是按左、根、右的顺序访问节点。一个朴素的思路是，先找到前序序列的第一个元素，将其作为头节点，然后通过遍历中序序列，找到中序序列对应的头节点位置，则中序序列中该位置之前的一定是当前节点的左子树部分，该位置之后的一定是当前节点的右子树部分。知道了左右子树的节点个数，我们便可以推导出前序序列中左右子树的分界点。这样我们便可以构建当前节点的左右子树，通过递归的方式，便可以构建出树中每一个节点。 上面的思路中是通过遍历中序序...

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

方法一（递归+剪枝） 1.题意整理 给定一颗二叉树。 判断该二叉树是否是平衡二叉树。 如果一颗二叉树是空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树，则这颗二叉树是平衡二叉树。 2.思路整理 一个朴素的想法是，先利用递归计算树中每颗子树的高度，然后再根据子树高度差的绝对值不超过1、并且左右子树都必须是平衡二叉树的条件，对整颗树进行递归。 代码如下： public class Solution { public boolean IsBalanced_Solution(TreeNode root) { //如果为空，直接返回true ...

方法一（BFS） 1.题意整理 给定一颗二叉树。 求二叉树的层序遍历。 2.思路整理 广度优先搜索的过程一般是将源节点入队，然后将当前节点出队，同时找到所有可到达的节点再次入队。循环这个过程，直到遍历完所有的节点。二叉树的层序遍历是一种特殊的广度优先搜索，当前队列中节点的个数即为当前层中节点数目，利用这个特点可以找到每一层的所有节点，依次加入到结果集。 首先新建一个队列，将根节点入队。 只要队列不为空，说明还可以继续遍历。当前队列大小即为当前层中节点个数。 每次遍历当前层所有节点，加入到临时list。遍历完之后加入到结果集。如果当前层节点的左右子节点不为空，则可以作为下一层节点加入到队列...

方法一（递归） 1.题意整理 给定一颗二叉树。 求二叉树的最大深度。深度是指树的根节点到任一叶子节点路径上节点的数量。 2.思路整理 按照二叉树递归的套路，需要考虑当前节点的情况、当前节点左子树的情况、当前节点右子树的情况。只要知道当前节点左右子树的深度，那么当前节点为根的子树的深度即为两者中较大的一个深度加1。 递归终止条件：root为空，直接返回0。 递归如何传递：每次需要往左右子树方向递归，只要直到左右子树深度，即可计算当前子树深度。 递归的返回值：返回当前子树深度。 图解展示： 3.代码实现 import java.util.*; /* * public class Tr...

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

方法一（递归） 1.题意整理 给定一颗二叉树，二叉树中每个节点对应一个节点值。 求二叉树中的最大路径和，其中路径指的是从任意节点出发到另一个节点之间所经过的路径。 2.思路整理 对于二叉树的大部分题目，都可以试图分三种情况进行考虑，分别是当前节点的情况、当前节点左子树的情况、当前节点右子树的情况。然后我们给递归的返回值一个含义，即对应节点为根的子树的贡献值。如下图所示，对于叶子节点2和-1，贡献值直接是节点本身，对于非叶子节点1，贡献值为当前节点值加上左右子树贡献值的较大者，如果某个子树贡献值小于0，则看作0来处理。 有了所有子树的贡献值之后，求最大路径和就好办了，只要计算当前节点加上左...

方法一（深度优先搜索） 1.题意整理 给定一颗二叉树，二叉树中每个节点对应一个节点值（在0-9范围内）。 求二叉树中所有路径的和，每一条路径指的是从根节点到某一个叶子节点这一串节点值从高位到低位组成的数。 2.思路整理 题目需要求所有路径和，所以只要找出每一条路径，然后记录对应路径的变化，最后将所有路径相加即可。可以采用深度优先搜索找路径，每次遇到叶子节点，则表示当前路径搜索完毕。 递归终止条件：当搜索完所有路径，递归终止，即root为空。 递归如何传递：每一次都会尝试往当前节点的左子节点和右子节点走，由于每次路径开始时，path都要重置为0，所以每次选择左子节点或右子节点之后，都会回溯...

题意整理 给定一个仅包含数字的字符串num和一个目标值target。 在num的数字之间添加"+","-"或"*",返回所有能够得到目标值的表达式。 方法一（位运算） 1.解题思路 可以分两步解决，第一步将运算符添加到字符串num，组成一个表达式，找到所有可能的表达式，第二步校验生成的表达式，计算表达式的值是否为target，如果是，则加入到结果中。 将运算符添加到num中的过程可以使用位运算，n个字符中总共有n-1个空可以插入运算符，每个空可以选择不插入、插入"+"、插入"-"、插入"*"。我们用00表示不插入、用01表示插入"+"、用10表示插入"-"、用11表示插入"*"。所以n-...

题意整理 给定n门课程，这n门课程中存在一定的依赖关系，例如想要完成B课程，必须先完成A课程。依赖关系存储在一个数组里。 找出可以完成所有课程的一个顺序列表，如果不能完成所有课程，返回一个空数组。 方法一（深度优先搜索） 1.解题思路 新建一个邻接表，记录所有课程对应的后置课程。新建一个visited数组，用于记录课程状态。0表示未访问，1表示已访问，2表示已完成。另外定义一个变量valid，判断是否存在循环依赖。 然后遍历所有课程，进行深度优先搜索。每次将当前课程标记为已访问，如果当前后置课程未访问，继续搜索，如果存在循环依赖，直接返回。 每完成一次搜索，标记为已完成。已完成的一定是递...