题目考察的知识点 二叉树的深度优先搜索 题目解答方法的文字分析 本题目由于二叉搜索树每一个节点都符合 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 以上3个定义，所以我们只需要递归判断二叉树的每一个节点是否都符合以上的定义即可。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * Tree...

题目考察的知识点 二叉树的层次遍历 题目解答方法的文字分析 首先定义 maxheight来保存牛的最大总重量，定义ans为具有牛的最大总重量的那一层的层数。因为牛的总重量和层数都不可能为负数，为此，初始化maxheight和ans为-1。然后层次遍历二叉树，用sum来保存当前层的牛的总重量，用ceng来保存当前层数。当sum>=maxheight时，修改maxheight和ans的值。当二叉树遍历完后，ans就是答案。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class Tree...

题目考察的知识点 二叉树的层次遍历 题目解答方法的文字分析 该题求我们按层数的奇偶来决定每一层的输出顺序。规定二叉树的根节点为第 0 层，如果当前层数是偶数，从左至右输出当前层的节点值，否则，从右至左输出当前层的节点值。因此我们通过层次遍历维护每一层的输出数组。同时维护一个isleft,当isleft为falses时，将得到的正序输出数组逆转成反序；为true则不需要做反转处理。然后用一个list将所有的输出数组装载,算法最后将它为int[][]类型。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * pub...

题目考察的知识点 二叉树的层次遍历 题目解答方法的文字分析 如果root==null,则返回空的字符串数组。否则，将二叉树每一层的字符串记录下来。这个主要使用二叉树的层次遍历实现。先遍历第一层根结点，将其左右非空孩子先后加入队列，利用队列先进先出的特点，使得同一层的节点依次输出，从而保证按层遍历二叉树。为了保证能够获得每一层的二叉树节点值组成的字符串，我们每次在进行下一层次的节点入队之前，先将上一层的节点个数记录下来，并记为count,由于队列是先进先出，所以，前count个节点就是上一层的所有节点。并用StringBuilder来记录每一层的字符串。最后再将字符串列表转换成字符串...

题目考察的知识点 二叉树的遍历以及基本性质，递归 题目解答方法的文字分析 从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null...

题目考察的知识点 二叉树的遍历以及基本性质 题目解答方法的文字分析 以为二叉树镜像对称，就是左右两边相等，也就是左子树和右子树是相当的。因此 可以使用深度优先搜索算法递归遍历左右子树，即要递归的比较左子树和右子树。 因为镜像的原因，假设a是左子树的根节点，b是右子树的根节点，则他们有以下的关系：a.left.val=b.right.val;b.left.val=a.right.val;同时等号两边的节点应该同时出现，否则不是镜像对称。根据上面信息可以总结出递归函数的两个条件： 终止条件： 1、left 和 right 不等，或者 left 和 right 都为空 2、递归的比较 l...

题目考察的知识点 二叉树的遍历 题目解答方法的文字分析 通过二叉树的深度优先搜索，将二叉树root1和二叉树root2的叶子节点从左到右记录在list1和list2中，然后反转list2,用java自带的比较方法，比较这两个list是否相同。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public T...

题目考察的知识点 链表的基本操作，动态规划 题目解答方法的文字分析 基本解题思路：当head是null，返回空链表；当原链表只有一个元素的时候，返回空链表，此时是回文的。剩下的情况就只需要判断原链表是否是回文串即可。首先将整个链表所代表的值用stringBuilder类型的sb存下来，然后用动态规划求出sb字符串的最大回文子串的首尾位置。最后通过首尾位置截取原链表的子链表。 字符串求最大回文子串：对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。根据这样的思路，我们就可以用动态规划的方法解决本题。我们用dp[i][j] 表示 ...

题目考察的知识点 二叉树的基本性质以及基本操作，二叉树的遍历方法 题目解答方法的文字分析 本题的解决方法：运用广度优先搜索来判断两个二叉树是否相同。本质上，两个二叉树是当作完全二叉树来存储的，同时将两个二叉树的每一个同位置的节点一起入队，每次取出两个节点进行位置和值的比较，如有不同，则结构不同. 算法步骤： 1、首先判断两棵二叉树的根节点是否为空，若都是空，则相同。否则为不同。 2、用一个队列存储两个二叉树的节点，初始时将两个二叉树的根节点分别加入同一个队列。每次从一个队列各取出2个节点，进行如下比较操作：首先比较两个节点是否都为空，若任一为空，则结构不相同。然后比较值是否相同，...

题目考察的知识点 二叉树的遍历，层次遍历 题目解答方法的文字分析 通过层次遍历，遍历整棵二叉树，同时在遍历的过程中比较maxHeight和各个结点的值，每一次比较将大于maxHeight的值保存到maxHeight中，遍历完整棵树后，也就得到了正确答案。 层次遍历：建立队列，用队列来保存元素。每次出队一个元素，同时将该元素的孩子节点加入队列中，直至队列中元素个数为0时，整棵二叉树遍历完毕。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class TreeNode { * int ...

题目考察的知识点 链表的基本操作，双指针判断回文串 题目解答方法的文字分析 基本思想：遍历链表，将链表的值用stringBuiler保存下来，然后通过双指针判断stringBuiler的值是否是回文串。 双指针判断回文串的算法解析：定义left和right分别为字符串的头和尾，不断比较left和right指向的字符是否相等，若不相等则不是回文字符串。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class ListNode { * int val; * ListNode n...

题目考察的知识点 考察链表的基本操作 题目解答方法的文字分析 算法思想:建立两个链表，分别收集值为1和值为0的结点，最后将这两个链表连在一起。 算法步骤： 1、建立哑结点oneDummy和zeroDummy，以便实现头插法来插入结点，创建tail结点来标识zeroDummy链表的尾巴。以便后续oneDummy和zeroDummy的结合 2、用cur结点遍历原链表，通过判断cur.val的值，来决定将cur结点插入oneDummy还是zeroDummy。 3、重复第二步，直到cur==null. 4、合并oneDummy和zeroDummy。即为答案 本题解析所用的编程语言 ...

题目考察的知识点 链表的插入与删除等基础操作，插入排序算法 题目解答方法的文字分析 插入排序的基本原理：维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 1，直到全部元素都加入到有序序列中。 算法简单描述： 1、判断head结点是否为null或者只有一个元素，如果是，则直接返回head即可。 2、创建哑节点 dummy，令 dummy.next = head。引入哑节点是为了便于在头节点之前插入节点。 3、创建lastSorted结点，它为链表的已排序部分的最后一个节点。cur指向当下的未排序的结点，当它为空时代表，所有未排...

题目考察的知识点 链表的基本操作 题目解答方法的文字分析 用一个listNode变量ret来维护合并的链表，遍历lists,每一个lists[i]都和ret进行链表的升序合并，最后答案保存到 ret中。 本题解析所用的编程语言 java 完整且正确的编程代码 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * ...