1.二叉树的中序遍历2.对称二叉树
3.寻找两个正序数组的中位数4.二叉树的最大深度5.相交链表
6.只出现一次的数字7.将有序数组转换为二叉搜索树8.买卖股票的最佳时机9.买卖股票的最佳时机II
10.验证回文串
1.二叉树的中序遍历1.二叉树的中序遍历
解题思路：
运用 栈+链表 的方式来实现
1.中序遍历：左根右；
2.需要先找到 左节点；
3.不断的寻找root.left，并且将所遍历的root.left放在栈中，直至找到最左边的节点；
4.找到了最左边的节点后，将栈顶元素出栈，将出栈的元素放在链表中，然后，将root节点 指向root.right;
5.然后再看root是否为空，如果不为空，继续进栈，root指向root.left;
6.如果root为空，出栈 栈顶元素，将出栈元素放在链表当中，然后，再将root节点指向root.right.
class Solution {
public static List inorderTraversal(TreeNode root) {
List list=new linkedList<>();
Stack stack=new Stack<>();
if(root==null){
return list;
}
while(root!=null || !stack.isEmpty()){
//遍历进栈，直到找到最左边的子节点
while(root!=null){
stack.push(root);
root=root.left;
}
//左边都遍历结束了
TreeNode node=stack.pop();
list.add(node.val);
root=node.right;
}
return list;
}
}
2.对称二叉树
2.对称二叉树
解题思路：
运用 函数调用的方式来实现这个题目；
1.判断root是否为空；
2.判断root节点的左节点的值 是否等于 右节点的值；
3.函数调用，判断left左边的节点值 是否等于 right右边节点的值；
判断left右边节点值 是否等于 right左边节点的值。
4.如果相对称的两个节点值不一样，或者 当 左边节点为空且右边节点不为空/左边节点不为空且右边节点为空的情况下，返回：false.
class Solution {
public boolean isSymmetric(TreeNode root) {
return judge(root,root);
}
public static boolean judge(TreeNode left,TreeNode right){
if(left==null && right==null){
return true;
}
while(left!=null && right!=null){
return (left.val==right.val)&&(judge(left.left,right.right))&&(judge(left.right,right.left));
}
return false;
}
}
3.寻找两个正序数组的中位数
3.寻找两个正序数组的中位数
解题思路：
1.重新构建一个数组，将这两个数组放在这个新的数组当中；
2.让这个新的数组进行排序；
3.如果新数组的长度是奇数，就取中间下标的那个数；
4.如果新数组的长度是偶数，就取中间两个元素下标对应的值，然后相加除以2.0，返回一个double类型的数。
import java.util.Arrays;
class Solution {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] array=new int[nums1.length+nums2.length];
for(int i=0;i
4.二叉树的最大深度
4.二叉树的最大深度
解题思路：
运用了递归调用的思路
1.如果root为空，返回0；
2.否则，分别调用root的左子树和右子树，选出最大的，最后结果再加一。
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
5.相交链表
5.相交链表
解题思路：
目的是：寻找两个链表的相交节点；
先取到两个链表的长度，看是否相同，要求是，将节点的起点设置成为一样的；
然后，进入循环，分别往后遍历，如果节点相同，就返回那个相同的节点，如果不同，则就两条链表，各自往后去取节点；
当退出循环时，就证明，没有相交节点，返回null。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null || headB==null){
return null;
}
int lenA=len(headA);
int lenB=len(headB);
ListNode tempA=headA;
ListNode tempB=headB;
while(lenA!=lenB){
if(lenA>lenB){
tempA=tempA.next;
lenA--;
}else{
tempB=tempB.next;
lenB--;
}
}
while(tempA!=null){
if(tempA==tempB){
return tempA;
}
tempA=tempA.next;
tempB=tempB.next;
}
return null;
}
public static int len(ListNode head){
int length=0;
while(head!=null){
length++;
head=head.next;
}
return length;
}
}
6.只出现一次的数字
6.只出现一次的数字
解题思路：
因为这个题目说可以不用额外的空间，所以，就不用hashMap来解决这个题目；
运用异或的方式来解决此题目；
这些都是十进制数字，异或的时候，应该转为二进制进行异或；
异或：相同为0，相异为1.
class Solution {
public int singleNumber(int[] nums) {
int result=0;
for(int i=0;i
7.将有序数组转换为二叉搜索树
7.将有序数组转换为二叉搜索树
解题思路：
二叉搜索树：左节点的值<中间节点的值<右节点的值；
高度平衡：要求左子树的高度 和 右子树的高度 差的绝对值<=1;
此题目 运用 递归调用的方法;
先找到中间节点，然后在递归调用中间节点左边的点，构成一个左子树，然后再调用中间节点右边的点，构成一个右子树。
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sorted2(nums,0,nums.length-1);
}
public static TreeNode sorted2(int[] nums,int low,int height){
if(low>height){
return null;
}
int mid=(low+height)/2;
TreeNode node=new TreeNode(nums[mid]);
node.left=sorted2(nums,low,mid-1);
node.right=sorted2(nums,mid+1,height);
return node;
}
}
8.买卖股票的最佳时机
8.买卖股票的最佳时机
解题思路：
确定两个变量，一个最大值，一个最小值；
遍历数组，当最小值小于数组元素时，更新最小值元素；
算出数组元素-最小值元素，更新最大值；
最终，返回最大值。
这个题目是后面的-前面的数组元素，取最大值，不取绝对值。
class Solution {
public int maxProfit(int[] prices) {
int min=Integer.MAX_VALUE;
int max=0;
for(int i=0;i prices[i]) {
min=prices[i];
}
int result=prices[i]-min;
if(max
9.买卖股票的最佳时机II
9.买卖股票的最佳时机II
解题思路：
设置一个最大值；
遍历整个数组，从1下标开始遍历；
只要当前下标元素大于前一个下标元素，最大值就加等于当前元素-前一个下标元素的值。
class Solution {
public int maxProfit(int[] prices) {
int max=0;
for(int i=1;iprices[i-1]){
max+=prices[i]-prices[i-1];
}
}
return max;
}
}
10.验证回文串
10.验证回文串
解题思路：
1.遍历数组，利用Character.isLetterOrDigit()，将字符串中的数字和字母挑选出来放在stringBuilder当中；
2.证明是否是回文，其特点就是：字符串正着读和反转读，结果都是一样的；
3.相互比较的时候，需要注意，equals比较的是两个字符串，这里不需要识别大小写，所以还需要利用String中的.toLowerCase(),将字符串改为小写；
4.先将stringBuilder先转为字符串，然后，再转成小写；
5.StringBuilder的字符串可以利用reverse()，将字符串反转，所以，先将stringBuilder反转后，再变为字符串，再改成小写；
6.将4，5得到的字符串相比较，如果一样，就是回文字符串；否则，就不是回文字符串。
class Solution {
public static boolean isPalindrome(String s) {
StringBuilder stringBuilder=new StringBuilder(s.length());
for(int i=0;i 
