本文按照牛客网的顺序，牛客网剑指offer刷题网址：https://www.nowcoder.com/ta/coding-interviews

本篇涉及的题目有：
1、顺时针打印矩阵
2、包含min函数的栈
3、栈的压入、弹出序列
4、从上往下打印二叉树
5、二叉搜索树的后序遍历序列
6、二叉树中和为某一值的路径

1、顺时针打印矩阵

问题描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路解析
1、首先可以看到，第一圈的第一个元素是（0，0），第二圈是（1，1），所以我们可以找到左上角元素的规律
2、这样，我们可以循环的打印每一圈的值，不过要注意最后一圈的情况
3、打印第一行不会有问题
4、打印第一列，要保证最后一圈至少有两行
5、打印第二行，不仅要至少有两行，而且至少有两列
6、打印第二列，我们至少要有三行，两列才可以

代码实现
java

import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        
        if(matrix.length == 0)
           return arr;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int start = 0;
        while(rows > start * 2 && cols > start * 2){
            printOneCircle(matrix,start,rows,cols);
            start += 1;
        }
        return arr;
    }
    
    public void printOneCircle(int[][] matrix,int start,int rows,int cols){
        int endrow = rows - start - 1;
        int endcol = cols - start - 1;
        for(int i=start;i<=endcol;i++){
            arr.add(matrix[start][i]);
        }
        if(endrow > start)
            for(int i = start+1;i<=endrow;i++){
                arr.add(matrix[i][endcol]);
            }
        if(endrow > start && endcol > start)
            for(int i=endcol - 1;i>=start;i--){
                arr.add(matrix[endrow][i]);
            }
        if(endrow > start + 1 && endcol > start)
            for(int i = endrow - 1;i>start;i--){
                arr.add(matrix[i][start]);
            }
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def __init__(self):
        self.res = []
    def printMatrix(self, matrix):
        # write code here
        if not matrix:
            return []
        start = 0
        rows = len(matrix)
        cols = len(matrix[0])
        while (rows > start * 2 and cols > start * 2):
            self.printOneCircle(matrix,rows,cols,start)
            start += 1
        return self.res
            
    def printOneCircle(self,matrix,rows,cols,start):
        endrow = rows - 1 - start
        endcol = cols - 1 - start
        for i in range(start,endcol+1):
            self.res.append(matrix[start][i])
        if endrow > start:
            for i in range(start+1,endrow+1):
                self.res.append(matrix[i][endcol])
        if endrow > start and endcol > start:
            for i in range(endcol-1,start-1,-1):
                self.res.append(matrix[endrow][i])
        if endcol > start and (endrow - start > 1):
            for i in range(endrow-1,start,-1):
                self.res.append(matrix[i][start])

2、包含min函数的栈

问题描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

思路解析
单独设计一个新栈，保存到当前栈顶时栈的最小元素。

代码实现
java

import java.util.Stack;

public class Solution {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> minStack = new Stack<Integer>();
    
    public void push(int node) {
        stack.push(node);
        if(minStack.empty() || node < minStack.peek())
            minStack.push(node);
        else
            minStack.push(minStack.peek());
    }
    
    public void pop() {
        if(!stack.empty()){
            stack.pop();
            minStack.pop();
        }
    }
    
    public int top() {
        if(!stack.empty()){
            return stack.peek();
        }
        else
            return -1;
    }
    
    public int min() {
        if(!minStack.empty())
            return minStack.peek();
        else
            return -1;
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.minStack = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.minStack or node < self.minStack[-1]:
            self.minStack.append(node)
        else:
            self.minStack.append(self.minStack[-1])
    def pop(self):
        # write code here
        if self.stack:
            self.stack.pop()
            self.minStack.pop()
    def top(self):
        # write code here
        if self.stack:
            return self.stack[-1]
        else:
            return None
    def min(self):
        # write code here
        if self.minStack:
            return self.minStack[-1]
        else:
            return None

3、栈的压入、弹出序列

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

思路解析
模拟两个栈的弹入弹出即可

代码实现
java

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++){
            if(pushA[i] == popA[index]){
                index += 1;
                continue;
            }
            stack.push(pushA[i]);
        }
        for(;index<popA.length;index++){
            if(popA[index]!=stack.pop())
                return false;
        }
        return true;
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        index = 0
        for i in pushV:
            if i == popV[index]:
                index = index + 1
                continue
            stack.append(i)
        while index < len(popV):
            if popV[index] != stack.pop():
                return False
            index = index + 1
        return True

4、从上往下打印二叉树

问题描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路解析
层次遍历的思路。

代码实现
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<Integer> PrintFromTopToBottom(TreeNode root) {
         ArrayList<Integer> list = new ArrayList<Integer>();
         if(root == null) return list;
         Deque<TreeNode> deque = new LinkedList<TreeNode>();
         
         deque.add(root);
         while(!deque.isEmpty()){
             TreeNode t = deque.pop();
             list.add(t.val);
             if(t.left != null) deque.add(t.left);
             if(t.right != null) deque.add(t.right);
         }
         return list;
     }
}

python

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            level = stack
            stack = []
            for node in level:
                res.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        return res

5、二叉搜索树的后序遍历序列

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

思路解析
递归进行判断，如果序列的长度小于等于2，那么一定是后序遍历的结果，否则根据BST和后序遍历的性质，遍历结果的最后一个一定是根节点，那么序列中前面一部分小于根节点的数是左子树，后面一部分是右子树，递归进行判断。

代码实现
java

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)
            return false;
        return isSequenceOfBST(sequence,0,sequence.length-1);
    }
    public boolean isSequenceOfBST(int[] sequence,int start,int end){
        if(end - start < 2)
            return true;
        int flag = sequence[end];
        int index = start;
        while(sequence[index] < flag)
            index += 1;
        int j = index;
        while(j<end){
            if(sequence[j] < flag)
                return false;
            j += 1;       
        }
        return isSequenceOfBST(sequence,start,index-1) && isSequenceOfBST(sequence,index,end-1);
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        # 7465 的问题
        # [] 的问题,即开始和中间过程中出现的[]的处理是不同的，所以定义了一个子函数
        if len(sequence) == 0:
            return False
        return self.verifySubSequenceOfBST(sequence)
        
    def verifySubSequenceOfBST(self, sequence):
        if len(sequence) < 3:
            return True
        flag = sequence[-1]
        index = 0
        while sequence[index] < flag:
            index = index + 1
        j = index
        while j < len(sequence) - 1:
            if sequence[j] > flag:
                j = j + 1
            else:
                return False
        return self.verifySubSequenceOfBST(sequence[:index]) and self.verifySubSequenceOfBST(sequence[index:-1])

6、二叉树中和为某一值的路径

问题描述
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路解析
定义一个子函数，输入的是当前的根节点、当前的路径以及还需要满足的数值，同时在子函数中运用回溯的方法进行判断。

代码实现
java

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 {
    public ArrayList<ArrayList<Integer>> arrs = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root==null)
            return arrs;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        subPath(root,arr,target);
        return arrs;
    }
    public void subPath(TreeNode node,ArrayList<Integer> arr,int target){
        if(node.left==null && node.right==null && target==node.val){
            arr.add(node.val);
            arrs.add(arr);
            return;
        }
        arr.add(node.val);
        ArrayList<Integer> left = (ArrayList<Integer>)arr.clone();
        ArrayList<Integer> right = (ArrayList<Integer>)arr.clone();
        arr = null;
        if(node.left!=null){
            subPath(node.left,left,target-node.val);
        }
        if(node.right!=null){
            subPath(node.right,right,target-node.val);
        }
    }
}

python

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.res = []
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        self.subPath(root,[],expectNumber)
        return self.res
        
        
    def subPath(self, root, path,number):
        if not root.left and not root.right:
            if number == root.val:
                self.res.append(path+[root.val])
            return
        if root.left:
            self.subPath(root.left,path+[root.val],number-root.val)
        if root.right:
            self.subPath(root.right,path+[root.val],number-root.val)