思路 对于二叉树搜索树来说，由于左子树全部值小于根节点值小于右子树全部值，所以我们定位元素的位置其实也简单。 对于两个元素位置一般就两种情况： 两个节点一个为父节点一个为子节点，那么这个父节点便是两个节点的祖先节点 两个节点位置相对一个在左一个在右，那么两个节点的祖先节点便是查找分叉时的根节点 代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(...

思路 使用递归的方法计算平衡二叉树的左右子树最大深度，在递归的每一层我们都判断一下当前节点的左右子树深度是否符合平衡二叉树条件，如果符合，返回最大深度，反之直接返回-1, 代码 public class Solution { public boolean IsBalanced_Solution(TreeNode root) { // 空树属于平衡二叉树 if (root == null) { return true; } // 默认根节点深度为0 // 创建变量接收返回最大深度 ...

思路 利用完全二叉树的特性递归的判断每棵子树是否符合完全二叉树的定义 或者也可以利用层序遍历的思想，在对传入二叉树进行层序遍历的同时，将值加入集合，当遇到某个节点有空节点时，加入占位元素到集合进行标记，每层遍历完，对集合进行遍历，如果占位元素是连续且后续没有元素值，说明该层符合完全二叉树的定义 代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(in...

思路 由于二叉排序树中序遍历是一个递增的有序序列，我们直接对传入的树进行中序遍历，如果输出序列不是递增的说明不是二叉排序树 也可以准备一个全局变量，记录遍历时的上一个节点的值，用当前值与上一个值的比较来取代原来加入当前节点值的逻辑，这样也可以 代码 思路一代码： import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * t...

思路 本题使用递归进行二叉树左右子树交换，先处理左右子节点的左右子节点的交换，最后再处理自身的左右子节点的交换 代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的...

思路 使用中序遍历的思想，设t1为主树，t2为合并树。 当两棵树的左子树均不为空则递归的调用合并方法进行合并。 如果主树的左子树为空而合并树的左子树不为空，则直接让合并树的左子树作为主树的左子树。 如果两棵树的左子树均为空或者合并树的左子树为空，则直接不管。 接着合并根节点，只需进行节点值的加操作即可。 接着参考左子树的处理进行编码即可思路是一样的，最后返回主树。 代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode...

思路 将二叉树进行层序遍历，对每一层遍历结束后的下一层辅助队列先进行奇偶校验，再进行回文校验。 注意，当某个节点的左子节点或者右子节点为空时需要添加占位节点，防止出现节点对称，但位置不对称的情况 代码 import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNod...

思路 使用分治思想，将大问题分割成一个个相同的小问题，创建一个递归方法，对传入的树进行双向链表化，使用二叉树的中序遍历遍历整个树的同时调用方法进行转换 注意递归方法的分情况讨论： 当传入节点为n0时，我们应当无任何操作 当传入节点为n1时，说明该节点不存在左子节点或者右子节点，我们只需要进行默认变换即可 如果传入节点为n2，说明该节点左右子树都存在，我们应当对其上一层调用返回该节点。 对于变换应当分默认变换与特殊变换： 默认变换：让当前节点的左子节点的后继指向当前节点(如果有的话)，当前节点的右子节点的前驱指向当前节点 特殊变换：因为返回值有左子节点或者右子节点，表明该节点为n2，需要...

思路 使用深度优先遍历来计算路径长度 代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ public boolean hasPat...

思路 使用深度优先遍历遍历二叉树的同时统计二叉树的最大深度 当然也可以利用层序遍历来计算二叉树的最大深度(记录层数) 代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * @param root TreeNode类 * @return int整型 */ public int ...

思路 让我们以根节点为第一层，可知奇数层从左到右遍历，偶数层从右向左，我们可以参考上一题的代码，只不过在遍历每层节点时判断当前是偶数层还是奇数层 代码 import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ...

思路 本题主要难点在于如何将当层遍历结果组成集合加入到结果集 利用队列来进行层序遍历，每当进行一层遍历时，统计当前队列中节点数创建相应大小本层结果集合进行接收，出队时，将出队节点子节点加入下层队列中 步骤： 主方法： 创建一个结果集合，创建一个初始辅助队列，并在根节点判空后将根节点加入队列中 将结果集合与辅助队列传入层序遍历方法中 返回结果集合 层序遍历方法： 统计本层队列节点总数，如果节点数等于0直接返回(方法出口)，通过节点数创建相应大小的本层结果集合 创建下层层序遍历所需要的辅助队列(这样就分离开了本层辅助队列与下层辅助队列) 使用while循环，循环中先将弹出节点的左右子节点加...

思路 参照题解思路，使用双指针标记左右边界，通过判断中间值与右边界的大小来逼近最小值所在位置，因为旋转数组的性质，右边界必定是原先有序数组前半部分的一部分，如果中间值小于右边界，说明最小值还在中点的左边，如果中间值大于右边界，说明最小值在中点的右边，如果中间值等于右边界，需要一步步减小右边界索引，来试探。 代码 import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int[] array) { if (array.length == 1) { ...

思路 该题并没有要求将全部的波峰找出，可以使用二分查找找到其中一个波峰即可 设置三个指针mid left right mid向左右比较，指向右边最大者时，更新左指针，反之则相反 直到左指针大于或者等于右指针时，就表明已经找到峰值结束循环返回。 不过有个毛病我很烦，就是当峰值处于边界时不太好判断，所以干脆直接硬编码了。如果有更好的优化思路，欢迎各位大佬提出来 代码 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * ...