剑指offer--让抽象具体化

题一：【包含min函数的栈】

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

分析：时间复杂度要求高，可牺牲空间。定义两个栈stack（正常操作）和stackMin（栈顶元素是最小值）。每次push时，直接向stack压入元素，并且和stackMin栈顶元素比较，如果要压入的数据较小则压入stackMin。弹出时，看stackMin是否为空或者两个栈的栈顶元素是否相等，如果相等，则两个栈都弹出一个元素。

import java.util.Stack;

public class Solution {
    //存放原数据，用于push、pop、top
    Stack<Integer> stack = new Stack<Integer>();
    //每次在stack添加数据时，进行比较，stackMin栈顶元素每次是当前最小值
    Stack<Integer> stackMin = new Stack<Integer>();
    public void push(int node) {
        stack.push(node);
        if(stackMin.empty()||stackMin.peek()>=node){
            stackMin.push(node);
        }
    }
    
    public void pop() {
        if((!stackMin.empty())&&stack.peek()==stackMin.peek()){
            stackMin.pop();
        }
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return stackMin.peek();
    }
}

题二：【栈的压入、弹出序列】

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

分析：新建一个栈stack按照压入顺序添加元素，每次添加完一个元素之后，比较此时栈顶元素和此时弹出序列元素是否相等，如果相等，stack立即弹出栈顶并且弹出序列遍历到下一个位置，循环比较栈顶和弹出序列直至不相等。再进行下一个元素的添加操作…

举例：压入顺序：1 2 3 4 5；弹出顺序：4 3 5 1 2；

1 1≠4 =》直接压入

2 2≠4 =》直接压入

3 3≠4 =》直接压入

4 4=4 =》压入，再弹出，弹出序列进入到下一个元素5 =》3≠5

5 5=5 =》压入，再弹出，弹出序列进入到下一个元素3 =》3=3 弹出，弹出序列进入到下一个元素2 =》…

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<Integer>();
        int index = 0;
        for(int i = 0;i < pushA.length; i++){
            stack.push(pushA[i]);
            if(stack.peek() != popA[index]){
                continue;
            }
            
            while(!stack.empty()&&stack.peek() == popA[index]){
                index = index+1;
                stack.pop();
            }
        }


        if(index == popA.length ) {
            return true;
        }
        return false;
        //或者直接 return stack.isEmpty();        
    }
}

题三：【从上往下打印二叉树】

从上往下打印出二叉树的每个节点，同层节点从左至右打印

分析：使用队列，先进先出，每遍历到一个节点，就将该节点的左节点和右节点加入队列中（先左后右）

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/


public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        //queue用来保存当前遍历到了哪个节点，一次性把一个节点的左右子都入队
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //list用来保存输出的节点
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root==null){//注意：空树返回一个默认构造的空LinkedList，而不是一个空指针null
            return list;
        }
        TreeNode current = root;
        queue.offer(current);
        //只要队列中还有节点就说明还没遍历完，继续。
        //每次从队列出队，然后将这个节点左右子入队列（FIFO，故能完成广度/层级遍历），再将这个节点记录在list中即可。
        while(!queue.isEmpty()){
            current = queue.poll();
            list.add(current.val);
            if(current.left!=null){//有左子则入队
                queue.offer(current.left);
            }
            if(current.right!=null){
                queue.offer(current.right);
            }
        }
        return list;
    }
}

题四：【二叉搜索树的后序遍历序列】

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

分析：使用递归----二叉搜索树特点，左节点比根节点小，右节点比根节点大。后序遍历的数组的最后一个元素是根节点，其前面数据能够分为两个子数组（子树），前面的小数组所有元素都比根节点小，后面的小数组所有元素都比根节点大，如果不满足就返回false。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0) return false;
        return VerifySquenceOfBST(sequence,0,sequence.length-1);
    }
    boolean VerifySquenceOfBST(int[] sequence, int left, int right){
        if(left>=right) return true;
        int mid = sequence[right];//当前子树根节点
        int i;
        for(i=left;i<right;i++){
            if(sequence[i]>mid) break;
        }
        for(int j=i;j<right;j++){
            if(sequence[j]<mid) return false;
        }
        return VerifySquenceOfBST(sequence,left,i-1)&&VerifySquenceOfBST(sequence,i,right-1);
    }
}

题五：【二叉树中和某一值的路径】

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> nodeList = new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root==null) return list;
        nodeList.add(root.val);
        target = target-root.val;
        if(target==0&&root.left==null&&root.right==null){
            list.add(new ArrayList<Integer>(nodeList));
        }
        FindPath(root.left,target);
        FindPath(root.right,target);
        nodeList.remove(nodeList.size()-1);
        return list;
    }
}