基本思路分段反转，那么每一段都可以看成子问题，因此可以用递归解决，每一层判断当前要遍历的链表节点是否为k个，如果不是k个就直接返回原链表，如果为k个就反转当前链表，反转后的链表再接上子问题中反转完的链表的头结点，最后返回当前反转链表的头结点。初始时要遍历一遍记录一个tail指针，用于判断是否为k个节点，如果为k个节点，遍历完后tail就指向当前反转链表的后面一个节点，也就是下一段要开始反转链表的第一个节点了，因此tail指针还可以作为当前链表反转的结束条件，因为要反转的是部分链表，所以不能用null作为结束条件，因为后面可能还有节点。参考参考题解 import java.util.*; /* ...

纠正思路初始思路是用尾插法，遍历到要开始反转的第m个位置时，保存好第m个位置的前一个节点和当前节点作为反转后的最后一个节点，以便于反转后和前面以及后面的节点进行连接，但是这样当反转是从第一个节点开始时，就很难处理空指针的问题，所以还是用头插法比较好。头插法需要设置一个额外的表头节点，其next指针永远指向链表第一个节点，初始时pre节点为表头节点，这样就可以在从第一个节点开始反转时也不会为空，遍历到要反转的位置后，pre就作为一个临时表头节点，指向反转后的第一个节点，current就作为反转后的最后一个节点，逐个将节点插到pre的后面，current前面。参考参考题解 import java....

基本思路二叉树先序遍历序列的第一个元素必然是根元素，而根据根元素在中序遍历序列中的位置就可以将序列分为左右子树，然后再递归按照左右子树序列来构建左右子树。基本思路是这样，但是不熟悉java的数组切片操作，所以还是看了题解，自己做的话可能就是for循环遍历中序序列，然后逐个将元素加入一个ArrayList了，这样太繁琐，而且要创建四个ArrayList，而java的Arrays.copyRangeOf方法就可以很方便的复制数组，只需要定位到中序遍历序列中根节点的位置就可以按照这个位置将先序遍历序列和中序遍历序列给分割开了。参考参考题解 import java.util.*; /* * publi...

基本思路序列化时采用先序遍历，遇到空节点则记录为#，并且每个节点序列化后面都加个分隔符","，这样方便序列化的字符串能够定位每个节点，str是引用地址，虽然每一层都会有一个新的引用地址的值，但是操作的都是引用地址所指向的内存的值。反序列化也采用先序遍历，先将字符串按分割符分割为节点数组，由数组下标记录当前创建的节点，再创建根节点记录数组的对应位置的元素，然后再递归创建左右子树，拼接到当前节点，要注意索引下标不能作为参数传入递归函数，这样每一层都会有一个新的索引下标，它是基本类型数据，传递的不是引用地址，所以还是用全局变量记录下标比较好。还需要注意java的字符串是用equa...

如何在二叉树中找到根节点到目标节点的路径二叉树不像二叉搜索树一样有序，因此需要递归寻找左子树和右子树，看看有没有目标节点，因此需要一个变量记录是否找到目标节点，在每一层将当前节点加入路径，如果当前节点是目标节点，则直接返回，路径数组是作为参数传入，在每一层改变的，如果当前节点不是目标节点，则到左右子树中找目标节点，找到后就会直接返回，没有找到则会将路径的最后一个节点，也就是每层刚加入的节点去除，因此递归返回时，当前层路径数组中就只有刚加入的节点了。参考参考题解 import java.util.*; /* * public class TreeNode { * int val = 0; * T...

如何获取公共祖先？要获取公共祖先，首先要获得根节点目标节点的路径，要获取路径就需要遍历二叉树将沿途的节点加入路径数组中，而二叉搜索树是有序的，可以根据节点的大小关系选择指针遍历，而不需要循环遍历，因为路径都是从根节点出发，所以两个目标节点的最远公共祖先是根节点，最近目标节点为两个目标节点的路径中最后一个相同的节点。参考参考链接 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int ...

基本思路按照平衡二叉树的定义，需要一个函数来计算左右子树的深度，然后根据左右子树深度的差值是否不超过1判断是否为平衡二叉树，并且还要递归进入左右子树判断左右子树是否为平衡二叉树。参考参考题解 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 { /** * 代码中...

利用层次遍历判断是否为完全二叉树层次遍历是从上到下，从左到右遍历，如果是完全二叉树，层次遍历的数组中出现null值的后面不应该再有节点值，因为完全二叉树叶子节点都在最左侧，因此可以在层次遍历中将null节点也加入队列，可以用一个布尔变量isComplete记录左边的节点是否为null，然后遇到null节点时将布尔变量设为true，表示后面不应该再有节点值了，如果符合完全二叉树，队列后面都是null值的话全都会被if判断拦截住，如果不符合，即isComplete为null，但是当前节点还有值，就返回false。参考参考题解 import java.util.*; /* * public clas...

纠正思路一开始是想将t2的节点全部都合并到t1，然后递归处理t1和t2的左子树的节点以及t1和t2右子树的节点，最后返回t1的根节点，但是这样处理t1为空t2不为空时，如果将t2的节点赋值给t1，就导致t1后面都有t2的节点了，而且t2节点为空时还会有空指针问题。正确做法应该是创建一个新的根节点，然后遍历t1和t2的左子树以及t1和t2的右子树，递归地拼接这个根节点的左子树和右子树，最后返回这个新创建的根节点。参考参考题解 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null...

如何判断对称？二叉树对称说明左子树的左结点和右子树的右节点相同，以及左子树的右节点和右子树的左结点相同，因此可以将二叉树分成两半，分别递归遍历比较左子树的左结点和右子树的右节点，以及左子树的右节点和右子树的左结点。参考参考题解 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class So...

如何将二叉搜索树转换为双向链表？二叉搜索树的左子树节点小于当前节点，右子树节点均大于当前节点，二叉搜索树的中序遍历可以得到一个有序序列，问题在于怎么将树的节点转换为链表的节点，由于需要返回有序链表的头结点，因此需要一个head指针记录链表的最左节点，而链表的最左节点就是二叉树的左子树遍历的最左节点，如何判断是否达到二叉树的最左节点呢？这就需要一个pre指针记录前驱节点来判断，pre指针初始化为null，当第一次到达二叉树的最左节点时，pre指针没有被修改过，所以pre==null时就是最左节点，而如果pre!=null，说明当前节点有前驱节点，需要修改前驱节点的右指针为当前节点，当前节点的左指...

递归分解问题题目要求根节点到叶子节点有没有等于sum值的路径，返回的是布尔值，因此可判断当前节点是否为叶子节点，如果是叶子节点就判断叶子节点的值是否为sum，如果不是则分解为子问题，即将sum减去当前值然后到左右子树中查找。题目返回的布尔值是自底向上从叶子节点依次返回的，即上一层的函数的返回值依赖于下一层的布尔值，并且每一层都加了||判断，如果左子树或右子树任何一个满足条件都会返回true，如果叶子节点的值不为sum，则他左右子树返回的结果必然为false。参考参考题解 import java.util.*; /* * public class TreeNode { * int val = 0...

基本思路难点在于不同层怎么按不同顺序打印节点值，不同层可以通过记录层数值判断是奇数层还是偶数层，打印节点值首先想的是如果偶数层就将队列中的下一层节点顺序反序，但是在for循环中加入下一层的节点一直是按左子树到右子树的顺序进行的，如果下一层节点的正确顺序为[5,7,9,11]，反转前队列中节点为[9,11,5,7]，反转后[7,5,11,9]，还是不对。正确做法是判断不同层后，将当前层数组保存的节点值反序就行了，因为数组中是从左到右的顺序存储节点，反转后是从右到左存储节点。 import java.util.*; /* * public class TreeNode { * int val = ...