题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。示例1输入[4,8,6,12,16,14,10]返回值true 解题思路思路：已知条件：后序序列最后一个值为root；二叉搜索树左子树值都比root小，右子树值都比root大。1、确定root；2、遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；3、遍历右子树，若发现有小于root的值，则直接返回false；4、分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。 易错点：不是根节...

题目描述输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。示例1输入[3,32,321]返回值"321323" 解题思路自定义比较器-比较两个数拼接之后的大小来确定元素的位置注意点：Collections.sort(list,comparator)中，比较器需要自己，但是比较器针对的是封装类，所以需要将int转换为包装类的list Java代码 import java.util.*; public class Solution { // public String Pr...

题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。示例1输入7返回值8 解题思路重点是对题意的理解-明确什么是丑数，就是在原来丑数的基础上不断的乘以2或3或5的操作，但是如果将其结果按从小到大排序是问题具体方法参考剑指offer的第一个题解Java代码 public class Solution { public int GetUglyNumber_Solution(int index) { if(index<=0) return 0; int p2...

题目描述牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？示例1输入"nowcoder. a am I"返回值"I am a nowcoder." 解题思路使用spilt()函数进行用空格分割得到字符串数组如果只有空格，即数组长度为0，则返回本身如果数组长度为1，则返回该字符否则就逆序...

题目描述将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0输入描述:输入一个字符串,包括数字字母符号,可以为空返回值描述:如果是合法的数值表达则返回该数字，否则返回0示例1输入"+2147483647"返回值2147483647示例2输入"1a33"返回值0 解题思路前判断前边是否有正负，记录下符号位之后判断各位是否为数字，然后计算即可 Java代码 public class Solution { public int StrToInt(String str) { if(str.length()==0) return 0; int f...

题目描述输入一个链表，按链表从尾到头的顺序返回一个ArrayList。示例1输入{67,0,24,58}返回值[58,24,0,67]解题思路方法一：利用ArrayList.add(index,val),每次都把结果插入到第0个位置方法二：直接进行递归-不通过方法三：直接遍历，之后再将ArrayList进行反转方法四：自己创建个栈，先把遍历结果存入栈中，最后再将栈内内容弹出放入ArrayList方法五：先将链表进行反转，之后再遍历 Java代码实现 /** * public class ListNode { * int val; * ListNode next = null; * * List...

题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007输入描述:题目保证输入的数组中没有的相同的数字 数据范围： 对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5示例1输入[1,2,3,4,5,6,7,0]返回值7 解题思路就是利用归并排序的思想进行逆序对的记数。因为每次进行归并排序，最后并的过程都会比较两个元素的大小，因此此时可以计算逆序对的个数...

题目描述请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。示例1输入{8,6,6,5,7,7,5}返回值true示例2输入{8,6,9,5,7,7,5}返回值false解题思路最暴力的方法--先将树进行前序遍历存储结构,再将树进行求镜像，再对镜像树进行前序遍历，比较遍历结果（如果节点值都一样，则不行--通过90%的用例）参考官方题解的最大的收获：找规律递归可以想到，但是因为一个根节点只有一棵树，下边有二棵子树，所以思路受限--可以用两个树来比较具体过程如下图官方题解java代码--注释的为暴力解法 /* public class Tr...

题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。示例1输入{5,4,#,3,#,2,#,1}返回值[5,4,3,2,1] 解题思路对二叉树进行层序遍历，输出结果 java代码 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 ArrayList<Integ...

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。示例1输入[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]返回值{1,2,5,3,4,6,7}解题思路利用中序遍历和前序遍历的特点进行递归求解前序遍历的第一个节点一定是根节点之后在中序里找到根节点。之前的是左子树的中序，之后的右子树的中序由于左右子树的前序和中序数目肯定相同，所以可以找到左右子树的前序之后进行递归java代码 /** * D...

题目描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。示例1输入{8,6,10,5,7,9,11}返回值[[8],[6,10],[5,7,9,11]]解题思路按照层序遍历的思想，利用队列先进先出进行实现先把根节点入队然后此时队列大小为本层的节点数然后进行本层的出队，出队之后就把它的左右孩子节点都入队java代码 import java.util.*; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { th...

题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。解题思路按照中序遍历的顺序就是排序的顺序。因此只需要在中序遍历中进行指针的改变用一个公共指针记录已遍历完成的前一个节点那么只需让当前节点的left指向公共节点，公共节点的right指向当前节点然后当前节点为公共节点即可之后就是递归 暴力思路就是用数组存储中序遍历的结果再按结果进行指针的修改，不再赘述bu***记录：必须分成两个函数与实现。因为涉及到递归，所以会执行多次中序，而最终查找头结点需要在递归完成之后，不然会修改指针的指向 ** java代码** /** public...

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。解题思路方法一：按照题意，分三步进行1.找到根节点2.进行中序遍历3.找出下一节点方法二：根据中序遍历的特点找规律规律的结论：如果该节点有右孩子节点，则下一节点为右孩子节点的最左孩子节点否则如果该节点是其父亲节点的左孩子节点，则下一节点为父亲节点否则该节点是其父亲节点的右孩子节点则判断其父亲节点和再父亲节点的关系如：5的父亲节点为2，但5是右孩子节点。所以判断2和6的关系，因为2是6的左孩子节点，所以结果是6。如果2是6的右孩子结点，则应再往上层走 /*...

题目描述给定一棵二叉搜索树，请找出其中的第k小的结点。示例1输入{5,3,7,2,4,6,8},3返回值{4}解题思路根据二叉搜索树的概念，一路向左，最左下是最小的，之后是右子树。然后递归到上一层完全遍历完左子树之后，再去右子树示例中{5,3,7,2,4,6,8}的树形结构为----5-- 3---7-2 4 6 8java代码实现 /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } ...