剑指offer记录

JZ1:二维数组中的查找

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-zuo/
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
分析：矩阵是从左到右递增、从上到下递增的，这是一个有规律的矩阵，从特殊的地方开始找目标值。

思路：
1.从左下角开始查找
2.从右上角开始查找
知识点：
代码实现(思路1)：

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length == 0  || array == null ){
          return false;
        }        
        int x = 0,y = array[0].length-1;        
        while( x < array.length && y >= 0 ){          
          if(array[x][y] == target){
            return true;
          }else if(array[x][y] > target){
              y--;
          }else{
              x++;
          }
        }
      return false;
    }
}

JZ2:替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy
分析：题目就是题解
思路：
方法1：直接使用String类的方法replace()
方法2：使用StringBuffer的方法append()，一个一个将原始字符和替换后的字符加进去
知识点：
String:不可变，因为是final声明的字符数组
StringBuffer：可变，加锁，线程安全，速度慢
StringBuilder：可变，不加锁，线程不安全，速度快
(String实现字符串相加的底层原理是先把String变为StringBuffer，再往里面添加字符串)
代码实现：

public class Solution {
    public String replaceSpace(StringBuffer str) {
      // return str.toString().replace(" ","%20"); //方式一
        StringBuffer result = new StringBuffer(); //方式二
        for(char ch : str.toString().toCharArray()){
          if(ch == ' ')
              result.append("%20");
          else
            result.append(ch);
        }
      return result.toString();
    }
}

JZ3:从尾到头打印链表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
分析：
可以使用递归或者非递归两种方式求解
思路：
1.递归方式
2.非递归方式
知识点：
1.递归与非递归
2.ArrayList的扩容机制：
包括jdk1.8和jdk1.7的区别：
jdk1.7:
jdk1.8:
待补充……
ArrayList的好的特性：是有序的，且每个元素必须挨着插入，如果删除或者插入很可能要前后移动大量元素位置
3.ArrayList和LinkedList的区别：
ArrayList：查找快，增删慢
LinkedList：查找慢。增删快
4.链表ListNode如何实现以及使用的
待补充……
代码实现：

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*/
//非递归方式
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        ListNode temp = listNode;
        while(temp != null){
          list.add(0,temp.val);
          temp = temp.next;
        }
        return list;
    }
}
//递归方式
import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
         if(listNode != null){
             printListFromTailToHead(listNode.next);
             list.add(listNode.val);
         }
        return list;
    }
}

此题补充力扣网站上的解法
方法一：递归法
解题思路：
利用递归： 先走至链表末端，回溯时依次将节点值加入列表 ，这样就可以实现链表值的倒序输出。
Java 算法流程：

1. 递推阶段： 每次传入 head.next ，以 head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。
2. 回溯阶段： 层层回溯时，将当前节点值加入列表，即tmp.add(head.val)。
3. 最终，将列表 tmp 转化为数组 res ，并返回即可。

复杂度分析：

• 时间复杂度O(N)： 遍历链表，递归 N 次。
• 空间复杂度O(N)： 系统递归需要使用 O(N) 的栈空间。

方法二：辅助栈法
解题思路：
链表特点： 只能从前至后访问每个节点。
题目要求： 倒序输出节点值。
这种 先入后出 的需求可以借助 栈 来实现。
算法流程：
入栈： 遍历链表，将各节点值 push 入栈。
出栈： 将各节点值 pop 出栈，存储于数组并返回。（PJava 新建一个数组，通过 popLast() 方法将各元素存入数组，实现倒序输出）。
复杂度分析：

• 时间复杂度 O(N)： 入栈和出栈共使用 O(N) 时间。
• 空间复杂度 O(N)： 辅助栈 stack 和数组 res 共使用 O(N) 的额外空间。

知识点：
1.LinkedList可以用来表示栈结构（Stack）
add(E e) 和 addLast(E e) ：将元素添加到栈结构得最后
public E removeLast()：返回最后一个元素，并且有返回值

//方式1：递归法
class Solution {
    ArrayList<Integer> list=new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res=new int[list.size()];
        for(int i=0;i<list.size();i++)
            res[i]=list.get(i);
        return res;
    }
    private void recur(ListNode node){
        if(node==null) return;
        recur(node.next);
        list.add(node.val);
    }
}
//方式2：辅助栈法
class Solution {
    public int[] reversePrint(ListNode head) {
       LinkedList<Integer> stack = new LinkedList<>();
       while (head!=null){
           stack.add(head.val);
           head=head.next;
       }
       int[] res=new int[stack.size()];
       for(int i=0;i<res.length;i++){
           res[i]=stack.removeLast();
       }
       return res;
    }
}
//方式3：自己的解法
class Solution {
    public int[] reversePrint(ListNode head) {
        ArrayList<Integer> list=new ArrayList<>();
        ListNode node=head;
        while(node!=null){
            list.add(0,node.val);
            node=node.next;
        }
        int[] res=new int[list.size()];
        for(int i=0;i<list.size();i++)
            res[i]=list.get(i);
        return res;
    }
}

JZ4:重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
分析：
使用递归与二叉树特点来求解

思路：
前序遍历和中序遍历就能唯一重构二叉树；不断划分为左子树和右子树(前序遍历第一个为root节点，中序遍历能确定root节点的左右子树，不断递归求解)
知识点：
1.递归思想
2.二叉树的前序、中序、后序遍历和重构
代码实现：

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode node = help(pre,in,0,pre.length-1,0,in.length-1);
        return node;
    }  
    private TreeNode help(int[] pre,int[] in,int preleft,int preright,int inleft,int inright){      
      if(preleft >= pre.length || inleft >= in.length || preleft > preright  || inleft >inright){
        return null;
      }   
      int rootValue = pre[preleft];
      TreeNode node = new TreeNode(rootValue);//根确定了，然后进行左右划分      
      int count = inleft;
      while(rootValue != in[count]){
        count++;
      }
      count -= inleft;      
      node.left = help(pre,in,preleft+1,preleft+count,inleft,inleft+count-1);
      node.right = help(pre,in,preleft+count+1,preright,inleft+count+1,inright);      
      return node;
  }
}

JZ5:用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
分析：读懂题目，利用栈和队列的特点来完成
思路：
栈是先进后出，用两个栈来实现队列先进先出(那么就同时只能有一个栈在进，一个栈在出才能实现)
知识点：
负责出栈的那个栈的元素只能是另一个栈放入的(并且是在负责出栈的那个栈为空的时候再入栈)
代码实现：

import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();    
    public void push(int node) {
        stack1.push(node);
    }    
    public int pop() {
      if(stack2.size()<=0){
        while(stack1.size()!= 0){
          stack2.push(stack1.pop());
        }
      }
      return stack2.pop();
    }
}

补充力扣网上的题解：
解题思路：

• 栈无法实现队列功能： 栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。
• 双栈可实现列表倒序： 设有含三个元素的栈 A=[1,2,3] 和空栈 B=[]。若循环执行 A 元素出栈并添加入栈 B ，直到栈 A 为空，则 A=[] , B=[3,2,1] ，即 栈 B 元素实现栈 A 元素倒序 。
• 利用栈 B 删除队首元素： 倒序后，B 执行出栈则相当于删除了 A 的栈底元素，即对应队首元素。

函数设计：
题目只要求实现 加入队尾appendTail() 和 删除队首deleteHead() 两个函数的正常工作，因此我们可以设计栈 A 用于加入队尾操作，栈 B 用于将元素倒序，从而实现删除队首元素。
加入队尾 appendTail()函数： 将数字 val 加入栈 A 即可。
删除队首deleteHead()函数： 有以下三种情况。

• 当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
• 否则，当 A 为空： 即两个栈都为空，无元素，因此返回 −1 。
• 否则： 将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。

复杂度分析：
由于问题特殊，以下分析仅满足添加 N 个元素并删除 N 个元素，即栈初始和结束状态下都为空的情况。

• 时间复杂度： appendTail()函数为 O(1) ；deleteHead() 函数在 N 次队首元素删除操作中总共需完成 N 个元素的倒序。
• 空间复杂度 O(N) ： 最差情况下，栈 A 和 B 共保存 N 个元素。

  class CQueue {
    LinkedList<Integer> A, B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    public void appendTail(int value) {
        A.addLast(value);
    }
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();//当栈 B 不为空,直接返回 B 的栈顶元素。
        if(A.isEmpty()) return -1;//当 A 为空： 即两个栈都为空，无元素，因此返回 −1
        while(!A.isEmpty())//(B为空但A不为空的情况)
            B.addLast(A.removeLast());
        return B.removeLast();
    }
  }

  JZ6:旋转数组的最小数字

  把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
  分析：
  这个题要用到非递减数组，同时解题容易出现漏洞的也是非递减排序；同时用旋转数组的特性进行求解。一般做查找的题先想到可以使用二分法查找；非递减数组旋转后变成了两个非递减数组
  思路：
  1.将middle和左端点进行比较(左端点作为目标target)
  2.将middle和右端点进行比较(右端点作为目标target)
  知识点：
  1.有序列可以使用二分查找：头、尾、中间值、目标值(没有目标值把头尾端点作为目标值)
  2.首先对入参进行边界值的判断，学会抛异常
  3.从题目给的非递减数组和旋转数组的本身特性入手
  代码实现： ```java //思路1:以左端点为目标 class Solution { public int minArray(int[] numbers) {

        if(numbers.length == 0){
          throw new RuntimeException("numbers is empty");
        }
        int begin = 0;
        int end = numbers.length - 1;
        int middle = 0;
        while(numbers[begin]>=numbers[end]){
          if((end-begin)==1){
            return numbers[end];
          }
          middle=(begin+end)/2;
          if(numbers[begin]<numbers[middle]){
            begin=middle;
          }else if(numbers[begin]>numbers[middle]){
            end=middle;
          }else{
            if(begin<end)
              begin++;
            else 
              break;  
          }        
        }
        return numbers[begin]; 

  } }

//思路2：以右端点为目标 import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length == 0){ throw new RuntimeException(“array is empty”); } int begin = 0; int end = array.length - 1; int middle = 0; while(array[begin]>=array[end]){ middle=(begin+end)/2; if(array[end]array[middle+1]){ return array[middle+1]; }
begin=middle+1; }else if(array[end]>array[middle]){ end=middle; }else{ end—; }
} return 0; } }

<a name="aae028520a082413c037bd0379d9f95d"></a>
### JZ7:斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。<br />分析：<br />需要知道斐波那契数列的特点  f(n)=f(n-1)+f(n-2)，说明只与前两项的和有关，只需关注前两项，从此处找到解题的突破口。<br />思路：<br />递归(很浪费时间)--->计划递归(仍浪费空间)--->动态规划(时间和空间上都做了优化)<br />1.递归：一个复杂问题不断分解为子问题，自顶向下分解，再自底向上返回去。需要重复分解很多次，时间复杂度高。<br />时间复杂度：O(n^2)  <br />空间复杂度：O(1)<br />2.计划递归(常规)：使用存储法，空间换时间的做法，把之前分解过的值都保存起来，解决重复分解浪费时间的问题，减少时间复杂度，但空间复杂度增加。<br />时间复杂度：O(n)   <br />空间复杂度：O(n)<br />3.计划递归优化(常规优化)：实际上我们只关心前两项，只需要存储下来前两项的值就可以计算出第三项的值，其余的值不需要存储，则可以使用两个变量来反复存储我们需要的前两项就可以，这个反复存储的过程相当于数组平行向右移动的过程，反复利用这两个变量，减少了空间复杂度，优化存储。<br />时间复杂度：O(n)   <br />空间复杂度：O(1)<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/8427696/1610692043336-2d7f1290-72ec-4281-b1df-d521d5f9c16d.png#height=228&id=XzhCe&margin=%5Bobject%20Object%5D&name=image.png&originHeight=228&originWidth=365&originalType=binary&ratio=1&size=9666&status=done&style=none&width=365)<br />知识点：<br />1.斐波那契数列特点：第三项的值等于前两项值的和(特点：只需关注前两项的值)<br />2.计划递归：用空间换时间<br />3.动态规划：计划递归的优化<br />4.从时间复杂度(减少计算次数)和空间复杂度(需要多少空间才给多少)来考虑优化<br />2.关于求余运算：（a+b)%p=(a%p+b%p)%p;<br />代码实现：
```java
//思路1：递归
public class Solution {
    public int Fibonacci(int n) {
        if(n<2){
          return n;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}
//思路2：计划递归
public class Solution {
    public int Fibonacci(int n) {        
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else{
            int[] result=new int[n+1];
            result[0]=0;
            result[1]=1;
            for(int i=2;i<=n;i++){
                result[i] = result[i-1]+result[i-2];
            }
            return result[n];
        }        
    }
}
//思路3：计划递归的优化
public class Solution {
    public int Fibonacci(int n) {
        if(n<2){
          return n;
        }
        int sum=0;
        int two=0;
        int one=1;
        for(int i=2;i<=n;i++){
          sum=one+two;
          two=one;
          one=sum;
        }
        return sum;
    }
}

JZ8:跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
分析：
状态 F(i)，状态方程 F(i)=F(i-1)+F(i-2)，最后跳的台阶个数是互斥的，即最后跳一级和最后跳两级
思路：
转换为斐波那契数列的求解，仅初始状态不同
知识点：
1.动态规划的运用
代码实现：

class Solution {
    public int numWays(int n) {
        if(n==0){
            return 1;
        }else if(n==1){
            return 1;
        }else{
          int sum = 0;
          int two = 1;
          int one = 1;
            for(int i=2;i<=n;i++){
                sum=(two+one)%1000000007;     
                two=one;
                one=sum;
            }
            return sum;
        }      
    }
}

JZ9:变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：
使用动态规划或者排列组合解题
思路：
1.动态规划求解：确定状态为 F(i)，确定状态转移方程 F(i)=2F(i-1)，初始状态为 F(1)=1，返回值为 F(n)=2^(n-1)[相当于是一个幂运算或者1的移位操作]
状态转移方程分析：
F(i)=F(i-1)+F(i-2)+F(i-3)+…+1 此方程的项数不确定，不好用代码实现，则分析：
F(i-1)=F(i-2)+F(i-3)+F(i-4)+…+1，
则 F(i)=2F(i-1) 项数是确定的，容易用代码实现
这是一个幂级运算或1的位移运算
2.排列组合求解：每个台阶跳与不跳都有两种选择，相当于是求一个排列组合。但最后一级台阶只有一种选择，那就是必须跳上去，从第1到第n-1级台阶都有2种选择，最后一级台阶只有1种选择：跳上去。
知识点：
1.动态规划状态、转移方程、初始状态、返回值的理解
代码实现：

public class Solution {
    public int JumpFloorII(int target) {
        if(target==0)
          return 1;
        return (1<<(target-1))%1000000007;
    }
}

JZ10:矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？比如n=3时，23的矩形块有3种覆盖方法。
分析：
分析状态 F(i)，状态转移方程 F(i)=F(i-1)+F(i-2)，初始状态 F(1)=1;F(2)=2,返回值是一个斐波那契数列的求解。
分析题目中：小矩形可以横着或者竖着，最后一步的状态转移操作可以有这两种方式，且这两种方式的最后一步是互斥不同的，没有重复。
思路：
使用动态规划解题
知识点：
转移方程：考虑通过一步的操作到当前状态的递推，只能一步操作。
代码实现：

public class Solution {
    public int rectCover(int target) {
        if(target<3){
          return target;
        }else{
          int sum=0;
          int two=1;
          int one=2;
          for(int i=3;i<=target;i++){
            sum=(one+two)%1000000007;
            two=one;
            one=sum;
          }
          return sum;
        }
    }
}

JZ11:二进制中1的个数

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
该题的另一种说法：(输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。)
分析：
int数据类型在内存中占用了4个字节，也就是32位。int类型是有符号的，因此，32位并不会全部用来存储数据，使用最高位来存储符号，最高位是0，提示数据是正数，最高位是1，表示数据是负数，使用其他的31位来存储数据。
思路：
1.二进制，使用与运算与移位运算来解题
2.使用java中的方法 Integer.bitCount(int n);
3.巧妙运用 n&(n-1) 能够消除掉n中的倒数第一个1，来计算n里包含1的个数
知识点：
1.java中的左移右移和无符号右移
<<表示左移，不分正负数，低位补0；　
>>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；
>>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位补0;
2.移位运算的高效性
3.原码、补码和反码
原码：是最简单的机器数表示法。用最高位表示符号位，‘1’表示负号，‘0’表示正号。其他位存放该数的二进制的绝对值。原码会出现+0和-0。
反码：正数的反码还是等于原码。负数的反码就是他的原码除符号位外，按位取反。
补码：正数的补码等于他的原码。负数的补码等于反码+1。
代码实现：

//思路1
public class Solution {
    public int NumberOf1(int n) {
        int count=0;
        while(n!=0){
            if((n&1)==1){
                count++;
            }
            n=n>>>1;
        }
        return count;
    }
}
//思路2
public class Solution {
    public int NumberOf1(int n) {
        return Integer.bitCount(n);
    }
}
//思路3
public class Solution {
    public int hammingWeight(int n) {
        int count=0;
        while(n!=0){//n!=0,说明至少有1个1，则先增加一次
          count++;
          n&=(n-1);//每与上一次则消灭一个1
        }
        return count;
    }
}

JZ12:数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题。
分析：
使用快速幂算法求解（快速幂是二分思想的一种，二分角度）
快速幂：快速计算底数的 n 次幂，时间复杂度 O(log2的n)，与原来的O(n)有了很大的提升
思路：
将 n 次幂不断的二分，偶数则直接二分，奇数则二分后再把多余的那一项乘进结果里面
知识点：
1.b>>>=1; 比 b=b>>>1;节省内存
2.(n&1)==1 运算表示 n 换算成二进制表示最后一位为1，也表示 n 是个奇数，也表示 n 不是2的次幂
3.(n>>>1) 无符号右移可以表示向下除2取整
代码实现：

class Solution {
    public double myPow(double x, int n) {
        long b=n;
        if(b<0){//负指数转为正指数计算
          b=-b;
          x=1/x;
        }
        double result=1;
        while(b!=0){
          if((b&1)==1){//当前幂为奇数，与运算判断奇偶
            result *= x;//当前幂为奇数，则需要将多余的那一项乘进结果里面
          }            
          x *= x;//x被替换成x^2
          b>>>=1;//右移1相当于向下取整
        }
        return result;
    }
}

JZ13:调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
分析：
分为需要考虑调整后数组里数的相对位置是否改变
思路：
1.不考虑相对位置：双指针法，头指针指向偶数，尾指针指向奇数，然后交换
2.考虑相对位置不变：找到了奇数，就往前插入
知识点：
1.排序算法
2.双指针算法
代码实现：

//思路1：不考虑相对位置
class Solution {
    public int[] exchange(int[] nums) {
        int head=0;//头指针
        int tail=nums.length-1;//尾指针
        int temp=0;
        while(head<tail){
          if((nums[head]&1)==0){//头指针指向了偶数
            if((nums[tail]&1)==1){//尾指针指向了奇数
                temp=nums[head];
                nums[head]=nums[tail];
                nums[tail]=temp;
                head++;
                tail--;
                continue;//交换了也直接跳过
            }
            tail--;//尾指针不是奇数直接跳过
            continue;
          }
          head++;//头指针不是偶数直接跳过
          continue;
        }  
        return nums;
    }
}
//优化思路1
class Solution {
    public int[] exchange(int[] nums) {
        int head=0;//头指针
        int tail=nums.length-1;//尾指针
        int temp=0;
        while(head<tail){
          while((head<tail)&&(nums[head]&1)==1) head++;
          while((head<tail)&&(nums[tail]&1)==0) tail--;
          temp=nums[head];
          nums[head]=nums[tail];
          nums[tail]=temp;
          head++;
          tail--;
        }  
        return nums;
    }
}
//思路2：考虑相对位置改变
public class Solution {
    public void reOrderArray(int [] array) {
      int i=0;//i表示已经将奇数放好的下一个位置，初始i=0表示一个奇数都还没有放好
      for(int j=0;j<array.length;j++){//j表示数组下标
        if((array[j]&1)==1){//奇数
          int temp = array[j];
          for(int k=j-1;k>=i;k--){//把从【i,j-1】的数都往后移动一个位置
            array[k+1]=array[k];//因为从前往后移动，所有倒着开始移动
          }
          array[i++]=temp;//把找到的这个奇数放到i的位置
        }
      }      
    }
}

JZ14:链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。
分析：


思路：
使用同向双指针，两个指针保持固定距离 k-1 的平移，就能找到倒数第 k 个元素
知识点：
快慢双指针问题(滑动窗口)
代码实现：

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {//运用同向双指针，滑动窗口解题
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k==0){
            return null;
        }
        ListNode front=head;
        ListNode behind=head;
        for(int i=1;i<k;i++){
            if(front.next == null)
                 return null;//如果链表的长度还没有k长，则返回null
            front =front.next;
        }//结束循环时，front已经指向第k个元素，然后behind在第一个，两者之间差了k-1个元素
        while(front.next!=null){
            front=front.next;
            behind=behind.next;
        }//跳出这个循环时，则front到了末尾，behind到了倒数第k个
        return behind;//返回找到的倒数第k个元素
    }
}
//同一种答案的不同写法(中间差k个或者差k-1个元素)
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(k==0) return null;
        ListNode front=pHead;
        ListNode after=pHead;
        for(int i=0;i<k;i++){
            if(front==null) return null;
            front=front.next;
        }//循环跳出时指向第k+1个节点
        while(front!=null){
            front=front.next;
            after=after.next;
        }
        return after;
    }
}

JZ15:反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
分析：
数组交换两个索引处元素的位置，需要三个变量，即：两个需要交换的元素和一个临时变量；
同样的，链表交换两个位置处的元素，需要3个指针，即：两个需要交换的指针和一个保存临时链表头的指针。


思路：
使用三个指针进行相邻两个位置元素的交换，然后交换一次(改变链表的 next 指向的元素)，这三个指针向后平移一次；需要注意：原链表的头元素变成尾元素，则这个元素的 next 应该置空 null，原链表的尾元素要变成头元素，则这个元素的 next 应该从 null 变成原链表的倒数第2个元素；这样才完成了链表的反转操作。
知识点：
1.链表一般是指单向链表，单向链表只有 next 元素，没有 pre 元素，所以在使用链表的时候，一定要记得先把链表的头指针保存下来，再运用其它指针遍历链表，头指针如果不保存就回不到头部了。
比如：
ListNode front=head;//保存头指针
ListNode curPot=head;//用这个指针来遍历链表
2.使用链表特别需要注意当前元素的 next 什么时候会指向 null，即指针到了尾元素的时候
3.注意链表不要成了环形链表，即尾指针的 next 为 null
代码实现：

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null){//说明链表为空，必须进行边界判断
            return null;
        }
        ListNode point_pre=head;
        ListNode point_cur=head.next;
        if(point_cur==null){//说明链表只有头元素
            return point_pre;
        }
        ListNode point_temp=point_cur.next;
        point_pre.next=null;//头元素要变为尾元素，则应把指向的下一个元素置空
        while(point_temp!=null){
            point_cur.next=point_pre;//反向重连
            //向后平移三个指针
            point_pre=point_cur;
            point_cur=point_temp;
            point_temp=point_temp.next;
        }//临时元素已经到了最后一个元素        
        point_cur.next=point_pre;//最后一个元素的下一个应该指向前一个
        return point_cur;
    }
}

JZ16:合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
分析：

思路：
1.创建一个新的链表，谁小则这个链表指向谁，并且把小的那个元素指针向后移，新链表同时也需要向后移
2.使用递归
知识点：
1.分离双指针的使用，遍历一个链表时，首先需要把头指针保存起来
2.递归知识点：
写递归代码，最重要的要明白递归函数的功能。可以不必关心递归函数的具体实现。
比如这个ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
函数功能：合并两个单链表，返回两个单链表头结点值小的那个节点。
如果知道了这个函数功能，那么接下来需要考虑2个问题：

     1. 递归函数结束的条件是什么？
     1. 递归函数一定是缩小递归区间的，那么下一步的递归区间是什么？

代码实现：

class ListNode {//单向链表
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
//思路1：双指针
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head1=list1;
        ListNode head2=list2;
        ListNode newHead=new ListNode(1);//新链表的头指针需要保存起来，哨兵
        ListNode temp=newHead;//移动头指针
        while(head2!=null&&head1!=null){
            if(head2.val>head1.val){//谁小则指向谁，并且后移
                temp.next=head1;
                head1=head1.next;
            }else{
                temp.next=head2;
                head2=head2.next;
            }
            temp=temp.next;//temp始终要指向新链表的末尾
        }
        //直接将剩余元素加到新链表的末尾
        if(head1!=null){
            temp.next=head1;
        }
        if(head2!=null){
            temp.next=head2;
        }
        return newHead.next;
    }
}
//思路2：递归
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
       if (list1 == null) {
            return list2;
       } else if (list2 == null) {
            return list1;
       }else{
            if(list1.val<list2.val){
                list1.next=Merge(list1.next, list2);
                return list1;
            }else {
                list2.next=Merge(list1, list2.next);
                return list2;
            }
        }
    }
}

JZ17: 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)。B是A的子结构， 即 A中有出现和B相同的结构和节点值。
分析：
若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B是否是树 A 的子结构，需完成以下两步工作：
1.先序遍历树 A 中的每个节点 nA (对应函数 isSubStructure(A, B))
2.判断树 A 中 以 nA 为根节点的子树 是否包含树 B (对应函数 recur(A, B))
recur(A, B) 函数
1.终止条件：
1.当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true ；
2.当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false ；
3.当节点 A 和 B 的值不同：说明匹配失败，返回 false ；
2.返回值：
1.判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left) ；
2.判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right) ；
isSubStructure(A, B) 函数：
1.特例处理： 当 树 A 为空 或 树 B 为空 时，直接返回 false ；
2.返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
1.以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)；
2.树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)；
3.树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)；
以上 2. 3. 实质上是在对树 A 做先序遍历 。
思路：
1.先在A树中找到与B树根节点值相同的节点P
2.以P节点作为根节点，与B树做比较
B树有的子节点，A树必须要
B树没有的子节点，A树可以有
知识点：
递归的使用
代码实现：

/**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
     if(root1==null || root2==null){//待比较的两个根如果有一个为空，则不用比了
          return false;
        }
        if(isContain(root1,root2)){//判断是否满足是树子结构
          return true;
        }
        //把A树的左右子节点当做根节点继续向下查找
        return HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
    }
    public boolean isContain(TreeNode node1, TreeNode node2){
        if(node1==null && node2!=null){
          return false;
        }
        if(node2==null){
          return true;
        }
        return node1.val==node2.val&&isContain(node1.left,node2.left)&&isContain(node1.right,node2.right);
    }
}
//优化内存占用
class Solution {
      public boolean isSubStructure(TreeNode A, TreeNode B) {         
          return (A!=null && B!=null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
      }
      boolean recur(TreeNode A, TreeNode B) {
          if(B == null) 
            return true;
          if(A == null || A.val != B.val) 
            return false;
          return recur(A.left, B.left) && recur(A.right, B.right);
      }
}

JZ18:二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。
分析：
方法一：递归法：

1. 终止条件： 当节点 root 为空时（即越过叶节点），则返回 null ；
2. 递推工作：
   1. 初始化节点 tmp ，用于暂存 root 的左子节点；
   2. 开启递归 右子节点 mirrorTree(root.right)，并将返回值作为 root 的 左子节点 。
   3. 开启递归 左子节点 mirrorTree(tmp)，并将返回值作为 root 的 右子节点 。
3. 返回值： 返回当前节点 root ；

Q： 为何需要暂存 root 的左子节点？
A： 在递归右子节点 “root.left = mirrorTree(root.right);” 执行完毕后， root.left 的值已经发生改变，此时递归左子节点 mirrorTree(root.left)则会出问题。
方法二:辅助栈(或队列)
利用栈（或队列)遍历树的所有节点node，并交换每个node的左/右子节点。算法流程:
1.特例处理:当root为空时，直接返回null ;
2初始化:栈（或队列)，本文用栈，并加入根节点root 。
3.循环交换:当栈stack为空时跳出;
1.出栈:记为node ;
2.添加子节点:将node左和右子节点入栈;
3.交换:交换node的左/右子节点。
4.返回值:返回根节点root 。
思路：
1.递归法
根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。
2.辅助栈
引入了栈数据结构（递归的实现原理也是栈，不过由系统自动完成），虽然这题使用辅助栈和递归的时间和空间复杂度都一样，但辅助栈占用的内存更多，使用的时间更长。
知识点：
1.关于递归,需要考虑2个问题：
1.递归函数结束的条件是什么？
2.递归函数一定是缩小递归区间的，那么下一步的递归区间是什么？
代码实现：

//递归法(无返回值)
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null){//递归的终止条件
            return null;
        }
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        mirrorTree(root.left);//只有递归到 root.left==null 时，这句函数才结束
        mirrorTree(root.right);//只有递归到 root.right==null 时，这句函数才结束
        return root;//这句只会执行一次
    }
}
//递归法(有返回值)
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) 
            return null;
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}
//辅助栈
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) //当 root 为空时，直接返回 null ；
            return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()) {//当栈 stack 为空时跳出
            TreeNode node = stack.pop();
            if(node.left != null) 
              stack.add(node.left);//左节点入栈
            if(node.right != null) 
              stack.add(node.right);//右节点入栈
            TreeNode tmp = node.left;//交换左右节点
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

JZ19:顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
分析：
根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5] 可以发现，顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。因此，考虑设定矩阵的“左、上、右、下”四个边界，模拟以上矩阵遍历顺序。

思路：
1.空值处理： 当 matrix 为空时，直接返回空列表 [] 即可。
2.初始化： 矩阵 左、右、上、下 四个边界 l , r , t , b ，用于打印的结果列表 res 。
3。循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环，每个方向打印中做以下三件事 （各方向的具体信息见下表） ；
根据边界打印，即将元素按顺序添加至列表 res 尾部；
边界向内收缩 1（代表已被打印）；
判断是否打印完毕（边界是否相遇），若打印完毕则跳出。
4.返回值： 返回 res 即可。
知识点：
给这个矩阵规划界限，并且不断缩小界限，打印完一行或一列就缩小一行或一列的界限；
注意判断打印完成的界限。
代码实现：

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int[][] matrix) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        if(matrix.length == 0) return list;
        int left=0,right=matrix[0].length-1,top=0,button=matrix.length-1;
        while(true){
          for(int i=left;i<=right;i++) list.add(matrix[top][i]);
          if(++top>button) break;
          for(int i=top;i<=button;i++) list.add(matrix[i][right]);
          if(left>--right) break;
          for(int i=right;i>=left;i--) list.add(matrix[button][i]);
          if(top>--button) break;
          for(int i=button;i>=top;i--) list.add(matrix[i][left]);
          if(++left>right) break;
        }
        return list;
    }
}

JZ20:包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
分析：
普通栈的 push() 和 pop() 函数的复杂度为 O(1)；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)
本题难点： 将 min() 函数复杂度降为 O(1) ，可通过建立辅助栈实现；
数据栈 A ： 栈 A 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
辅助栈 B ： 栈 B 中存储栈 A 中所有 非严格降序 的元素，则栈 A 中的最小元素始终对应栈 B 的栈顶元素，即 min() 函数只需返回栈 B 的栈顶元素即可。
因此，只需设法维护好 栈 B 的元素，使其保持非严格降序，即可实现 min() 函数的 O(1)复杂度。

思路：
函数设计：
push(x) 函数： 重点为保持栈 B 的元素是非严格降序 的。
将 xx 压入栈 A （即 A.add(x) ）；
若 ① 栈 B 为空 或 ② xx 小于等于 栈 B 的栈顶元素，则将 xx 压入栈 B （即 B.add(x) ）。
pop() 函数： 重点为保持栈 A, B 的 元素一致性 。
执行栈 A 出栈（即 A.pop() ），将出栈元素记为 y ；
若 y 等于栈 B 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）。
top() 函数： 直接返回栈 A 的栈顶元素即可，即返回 A.peek() 。
min() 函数： 直接返回栈 B 的栈顶元素即可，即返回 B.peek() 。
知识点：
1.关于栈的使用
Stack<> s1=new Stack<>();
s1.pop();//弹出栈顶元素并删除，使用一次则弹出一次
s1.peek();//查看栈顶元素不删除
s1.add(xxx);//添加一个元素到栈顶，但返回值是boolean类型，添加是否成功
s1.push(xxx);//添加一个元素到栈顶，但返回值是当前添加进去的值
代码实现：

import java.util.Stack;
public class Solution { 
    Stack<Integer> stoStk;
    Stack<Integer> minStk;
    public Solution() {
        stoStk=new Stack<>();
        minStk=new Stack<>();
    }
    public void push(int node) {
        stoStk.add(node);
        if( minStk.empty() || minStk.peek()>=node)
            minStk.add(node);
    }    
    public void pop() {
        if(stoStk.pop().equals(minStk.peek()))
            minStk.pop();
    }    
    public int top() {
        return stoStk.peek();
    }    
    public int min() {
        return minStk.peek();
    }
}

JZ21: 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
分析：
给定一个压入序列 pushed 和弹出序列 popped，则压入和 弹出操作的顺序（即排列）是唯一确定的。
考虑借用一个辅助栈 stack ，模拟 压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。
入栈操作： 按照压栈序列的顺序执行。
出栈操作： 每次入栈后，循环判断 “栈顶元素 == 弹出序列的当前元素” 是否成立，将符合弹出序列顺序的栈顶元素全部弹出。
由于题目规定 栈的所有数字均不相等 ，因此在循环入栈中，每个元素出栈的位置的可能性是唯一的（若有重复数字，则具有多个可出栈的位置）。因而，在遇到 “栈顶元素 == 弹出序列的当前元素” 就应立即执行出栈。
思路：
算法流程:
1.初始化:辅助栈stack，弹出序列的索引i;
2.遍历压栈序列:各元素记为num ;
1.元素num入栈;
⒉.循环出栈:若stack的栈顶元素=弹出序列元素popped[i]，则执行出栈与i++;
3.返回值:若stack为空，则此弹出序列合法。
复杂度分析:
时间复杂度O(N):其中N为列表pushed的长度;每个元素最多入栈与出栈一次，即最多共2N次出入栈操作。
空间复杂度O(N):辅助栈stack最多同时存储N个元素。
知识点：
1.栈的先入先出的特点
2.合理运用模拟栈
代码实现：

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {        
        Stack<Integer> stack=new Stack<Integer>();//根据是否模拟成功，即可得到结果。
        int i=0;
        for(int num:pushed){
            stack.add(num);
            while(!stack.empty()&&stack.peek()==popped[i]){
                stack.pop();
                i++;
            }
        }
        return stack.empty();//如果栈内元素不为空，则表示不是出栈顺序
    }
}

JZ22-1:从上往下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。(从上到下打印二叉树 I )
分析：

• 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。
• BFS 通常借助 队列 的先入先出特性来实现。

思路：
算法流程:
1.特例处理:当树的根节点为空，则直接返回空列表;
2.初始化:初始化印结果列表res，初始化包含根节点的队列queue = [root] ;
3.BFS循环:当队列queue为空时跳出;
1.出队:队首元素出队，记为node ;
2.打印:将node.val添加至列表res尾部;
3.添加子节点:若node的左(右)子节点不为空，则将左(右)子节点加入队列queue;
4.返回值:返回打印结果列表res 即可。
知识点：
1.ArrayList 想要变成数组的话，只能挨个遍历
2.队列的实现类可以使用 LinkedList : Queue queue = new LinkedList<>();
队列判断是否为空：queue.isEmpty()
3.树的话每个节点都需要 new TreeNode(xxx)
代码实现：

import java.util.*;
public class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null)
            return new int[0];
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        ArrayList<Integer> ans = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left != null)
                queue.add(node.left);
            if(node.right != null)
                queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }
}

JZ22-2:JZ60:把二叉树打印成多行

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。(从上到下打印二叉树 II )
分析：
I. 按层打印： 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。BFS 通常借助 队列 的先入先出特性来实现。
II. 每层打印到一行： 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。
思路：
算法流程:
1.特例处理:当根节点为空，则返回空列表[];
2.初始化:初始化打印结果列表res，初始化包含根节点的队列queue = [root] ;
3.BFS循环:当队列queue 为空时跳出;
1.新建一个临时列表tmp，用于存储当前层打印结果;
2.当前层打印循环:循环次数为当前层节点数（即队列queue长度);
1.出队:队首元素出队，记为node ;
2.打印:将node.val添加至tmp尾部;
3.添加子节点:若node的左(右）子节点不为空，则将左(右)子节点加入队列queue
3.将当前层结果tmp添加入res 。
4.返回值:返回打印结果列表res 即可。
知识点：
1.使用 List 和 ArrayList 的时候时，嵌套多层泛型时候，泛型类型必须一模一样
例如：List> arrList=new ArrayList>();或者省略
List> arrList=new ArrayList<>();
2.for(int i=queue.size();i>0;i—){
这句代码是实现分层打印的精髓；把 i 的初始值设置为 queue.size()；则只会初始进入 for 时的这一次；但是如果错误的把 i 的终止条件设置为 queue.size()；则会导致终止条件随时在发生改变(因为 queue.size() 会在循环体内发生改变)，则应该把 queue.size() 设置为 for 循环的初始化条件。
3.集合中有方法：Collections.reverse(集合对象)；//反转
代码实现：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            if(res.size() % 2 == 1) Collections.reverse(tmp);
            res.add(tmp);
        }
        return res;
    }
}

JZ22-3:JZ59:按之字形顺序打印二叉树

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。(从上到下打印二叉树 III )
分析：
思路：
方法一:层序遍历＋双端队列
。利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列)tmp，并规定:
。奇数层则添加至tmp尾部，
。偶数层则添加至tmp头部。
复杂度分析:
。时间复杂度 O(N) ：N 为二叉树的节点数量，即 BFS 需循环 N 次，占用 O(N) ；双端队列的队首和队尾的添加和删除操作的时间复杂度均为 O(1) 。
。空间复杂度 O(N) ： 最差情况下，即当树为满二叉树时，最多有 N/2 个树节点 同时 在 deque 中，使用 O(N) 大小的额外空间。
方法三:层序遍历＋倒序
。此方法的优点是只用列表即可，无需其他数据结构。
。偶数层倒序:若res的长度为奇数，说明当前是偶数层，则对tmp执行倒序操作。
复杂度分析:
。时间复杂度O(N):N为二叉树的节点数量，即BFS需循环N次，占用O(N)。共完成少于N个节点的倒序操作，占用O(N)。
。空间复杂度O(N)︰最差情况下，即当树为满二叉树时，最多有N/2个树节点同时在queue 中，使用O(N)大小的额外空间。
知识点：
1.Java 中将链表 LinkedList 作为双端队列使用。有方法addFirst()与addLast()
addFirst():加入队列头部
addLast():加入队列尾部
代码实现：

//方法一:层序遍历＋双端队列
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) tmp.addLast(node.val); // 奇数层 -> 队列尾部
                else tmp.addFirst(node.val); // 偶数层 -> 队列头部
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}
//方法三:层序遍历＋倒序
import java.util.*;
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            if(res.size() % 2 == 1) Collections.reverse(tmp);
            res.add(tmp);
        }
        return res;
    }
    public static void main(String[] args) {
        TreeNode tree1=new TreeNode(3);
        tree1.left=new TreeNode(9);
        TreeNode tree2=new TreeNode(20);
        tree1.right=tree2;
        tree2.left=new TreeNode(15);
        tree2.right=new TreeNode(7);
        List<List<Integer>> lists = new Solution().levelOrder(tree1);
        for (List<Integer> list : lists){
            System.out.println(list);
        }
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

JZ23:二叉搜索树的后序遍历路径

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。
分析：
后序遍历定义： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。
二叉搜索树定义： 左子树中所有节点的值 <根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。

思路：
1.递归方式1：
2.递归方式2：根据二叉搜索树的定义，可以通过递归，判断所有子树的 正确性 （即其后序遍历是否满足二叉搜索树的定义） ，若所有子树都正确，则此序列为二叉搜索树的后序遍历。

  - 递归解析
     - 终止条件:当i≥j，说明此子树节点数量≤1，无需判别正确性，因此直接返回true ;
     - 递推工作:

1.划分左右子树:遍历后序遍历的 [i,j] 区间元素，寻找第一个大于根节点的节点，索引记为m。此时，可划分出左子树区间[i,m -1]、右子树区间[m,j-1]、根节点索引 j 。
2.判断是否为二叉搜索树:
左子树区间 [i, m-1] 内的所有节点都应右子树区间 [m,j-1] 内的所有节点都应>postorderlj]。实现方式为遍历，当遇到≤postorder[j]的节点则跳出;则可通过 p==j 判断是否为二叉搜索树。

  - 返回值:所有子树都需正确才可判定正确，因此使用与逻辑符&&连接。

1.p==j︰判断此树是否正确。
2.recur(i, m - 1):判断此树的左子树是否正确。
3.recur(m,j - 1):判断此树的右子树是否正确。
3.方法二：辅助单调栈
后序遍历倒序： [ 根节点 | 右子树 | 左子树 ] 。类似 先序遍历的镜像 ，即先序遍历为 “根、左、右” 的顺序，而后序遍历的倒序为 “根、右、左” 顺序。


知识点：

代码实现：

//递归方式1：
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length<1) 
           return true;
       ArrayList<Integer> list= new ArrayList<>();
       for(int num:postorder){
           list.add(num);
       }
       return isConverse(list);
    }
    public boolean isConverse(ArrayList<Integer> list){
        if(list.size()<1)
            return true;
        int root=list.get(list.size()-1);
        int i=0;
        ArrayList<Integer> left=new ArrayList<Integer>();
        ArrayList<Integer> right=new ArrayList<Integer>();
        while(root>list.get(i)){
            left.add(list.get(i++));
        }
        while(root<list.get(i)){
            left.add(list.get(i++));
        }
        if(i<list.size()-1)
            return false;
        return isConverse(left)&&isConverse(right);
    }
}
//递归方式2
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;//说明此节点已经没有子树了
        int p = i;
        while(postorder[p] < postorder[j]) p++;//找遍左子树
        int m = p;
        while(postorder[p] > postorder[j]) p++;//找遍右子树
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}
//方法二：辅助单调栈
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }
}