16.合并两个排序的链表

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

递归

把较小的那个节点当做每一层的初始节点，他的next节点为下一层的结果
返回条件：其中一个节点为空
递归结构：小的节点的next是函数执行的结果

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        if pHead1.val<pHead2.val:
            pHead1.next=self.Merge(pHead1.next,pHead2)
            return pHead1
        else :
            pHead2.next=self.Merge(pHead1,pHead2.next)
            return pHead2

17.树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

递归判断

  1. 有一个函数a，能够判断两棵树是否相同
  2. 不断将pRoot1的子树与pRoot2放到函数中比较

返回条件：1、其中一个为空，2、两子树相同
递归结构：左子树和右子树继续比较

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        #辅助函数，判断两树是否相同
        def isSame(pRoot1,pRoot2):
            if not pRoot2: #必须先判断pRoot2，如果先 if not pRoot1,即使两树相同，此时pRoot1也为空，返回Fasle
                return True
            if not pRoot1 or pRoot1.val!=pRoot2.val: #不能颠倒顺序，否则pRoot1.val可能为空就比较，会报错
                return False
            return isSame(pRoot1.left,pRoot2.left) and isSame(pRoot1.right,pRoot2.right)
        #返回条件，1、其中一个为空，2、两子树相同
        if not pRoot1 or not pRoot2:
            return False
        if isSame(pRoot1,pRoot2):
            return True
        #递归结构，左子树和右子树继续比较
        return self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2)

18.二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

递归大法（再写递归递不动了）

题目没有要求要返回节点，原地修改root节点即可，加上return也行
返回条件：为空
递归结构：我们只需要保证对每个节点，都交换他的左右节点即可，然后继续往下

class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if not root:
            return None
        root.left,root.right=root.right,root.left
        self.Mirror(root.left)
        self.Mirror(root.right)

19 .顺时针打印矩阵

这个题目很经典，也有点难度
以下解法，基本是看了大佬思路才做出来的

缩减矩阵

直接按照顺序将矩阵添加到res列表中
注意:
append添加单个元素，如果添加list，将会把整个list当做一个对象
extend添加整个列表中的单个元素，list中有多少添加多少

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        res=[]
        while matrix:
            res.extend(matrix.pop(0))
            if matrix and matrix[0]:  #matrix不为空但是matrix[0]可能为空,如[[]，[]，[]]
                for r in matrix: 
                    res.append(r.pop()) #pop函数默认抛出最后一个元素
            if matrix:
                res.extend(matrix.pop()[::-1])  #抛出最后一行并将此行逆序加入到res中
            if matrix and matrix[0]:
                for r in reversed(matrix):
                    res.append(r.pop(0))
        return res

当然，这个方法破坏了矩阵
我们看到，如果走完一圈之后，整个矩阵缩了一圈，我们可以从matrix[1][1]继续出发，当然，其他边界也会相应变化

20.包含min函数的栈

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

两个栈解法

一个栈常规操作，一个栈只保存最小值，这里有个难点是push()函数中，即使node>stack2[-1]了，也要再加一遍stack2[-1]，是为了确保两个栈数量一样
所以在pop中，两个栈也都要pop()出数据，但是只返回常规栈中的节点

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