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

方法一（递归） 1.题意整理 给定彼此独立的两棵二叉树t1和t2，树中节点各不相同。 判断t2是否是t1的子树。 2.思路整理 首先定义一个函数，用来判断两颗树是否完全相同。然后根据这个函数，通过递归的方式遍历t1中所有的子树，看有没有和t2完全相同的。 递归终止条件：如果root1、root2同时为空，说明所有节点都满足要求，返回true。如果root1为空，root2不为空或者root2为空，root1不为空，说明不满足要求，返回false。 递归如何传递：每次递归，都要比较当前节点root1和root2相等，同时比较root1左子节点是否等于root2左子节点，root1右子节点是...

方法一（栈） 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，所以每次选择左子节点或右子节点之后，都会回溯...