剑指Offer|牛客网——python之剑指0ffer之67道在线编程——jz16-jz20 二叉树|算法|链表

剑指0ffer—67道在线编程—jz16~jz20

jz16 合并两个排序的链表
jz17 树的子结构
jz18 二叉树的镜像
jz19 顺时针打印矩阵
jz20 包含min函数的栈

jz16 合并两个排序的链表题目描述
【剑指Offer|牛客网——python之剑指0ffer之67道在线编程——jz16-jz20】输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
题目链接
思路分析：
见之前刷题笔记2020-05-27—力扣刷刷5-21.合并两个有序链表
jz17 树的子结构题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
题目链接
思路分析：
子结构定义：树A和树B的根结点相等，并且树A的左子树和树B的左子树相等，树A的右子树和树B的右子树相等

如果A树和B树的根节点值相同，则去判断A中是否有B子结构
- 如果A树和B树的节点值相同，则去判断A的左右子树中是否有B的左右子树子结构
如果没有，则从A的左子树中找是否有B子结构
如果还没有，则从A的右子树中找是否有B子结构

【代码实现】

# -*- coding:utf-8 -*- # class TreeNode: #def __init__(self, x): #self.val = x #self.left = None #self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): # write code here if not pRoot1 or not pRoot2:#如果两者有一个为空树，则返回false return False """ A,B的根结点相同； A的左子树与B相同 A的右子树与B相同三者成立之一，返回true """ res01=self.is_subtree(pRoot1,pRoot2) or self.HasSubtree(pRoot1.left, pRoot2)or self.HasSubtree(pRoot1.right, pRoot2) return res01 def is_subtree(self,A,B): if not B:#若B不存在时，返回true return True if not A or A.val!=B.val: return False res02=self.is_subtree(A.left, B.left) and self.is_subtree(A.right, B.right)#A,B的左子树与右子树均相等时，返回True. return res02

jz18 二叉树的镜像题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。

剑指Offer|牛客网——python之剑指0ffer之67道在线编程——jz16-jz20

文章图片

题目链接
思路分析：
观察原二叉树与镜像二叉树，发现相对于原二叉树，结点的左右孩子互换，左右孩子的子树也做了相同的互换。

# -*- coding:utf-8 -*- # class TreeNode: #def __init__(self, x): #self.val = x #self.left = None #self.right = None class Solution: # 返回镜像树的根节点 def Mirror(self, root): # write code here if root: root.left,root.right=root.right,root.left#左子树与右子树互换 self.Mirror(root.left)#左子树的叶左右节点互换 self.Mirror(root.right)#右子树的叶左右节点互换

jz19 顺时针打印矩阵题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.
题目链接
思路分析：

文章图片

【代码实现】

# -*- coding:utf-8 -*- class Solution: # matrix类型为二维列表，需要返回列表 def printMatrix(self, matrix): # write code here res=[] while matrix:#判断matrix是否为空 if matrix: #1、取出矩阵的第一行【1，2，3，4】，移动到res列表中，此时，矩阵剩余三行 res+=matrix.pop(0) #2、循环将矩阵每行，最后一个元素【8，12，6】；移动到res列表中 if matrix and matrix[0]: for row in matrix: res.append(row.pop()) #3、取出矩阵的最后一行，然后再倒叙【15，14，13】，移动到res列表中 if matrix: res+=matrix.pop()[::-1] #4、先对矩阵元素即每行倒叙，再将每行的最后一个元素[9,5]，移动到res列表中 if matrix and matrix[0]: for row in matrix[::-1]: res.append(row.pop(0)) #5、上边进行处理后，此时剩余中间的那一环，进入下一轮循环 return res

jz20 包含min函数的栈题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。
题目链接
思路分析：
双栈法
首先需要一个正常栈stack,用于栈的正常操作，然后需要一个辅助栈minstack，专门用于获取最小值，具体操作如下。

文章图片

push操作就如图片上操作。
pop操作直接对应弹出就好了。
top操作就返回stack的栈顶
min操作就返回stack的栈顶
【代码实现】

# -*- coding:utf-8 -*- class Solution: def __init__(self): self.stack=[] self.minstack=[] def push(self, node): self.stack.append(node) #如果minstack为空或值比栈顶元素小；if not aa 表示如果aa等于空就是true ifnot self.minstackor node<=self.minstack[-1]: self.minstack.append(node) else: self.minstack.append(self.minstack[-1])def pop(self): if not self.stack: self.stack.pop() self.minstack.pop() def top(self): return self.stack[-1]#直接返回stack的末尾 def min(self): return self.minstack[-1]#直接返回minstack的末尾

时间复杂度：O(1)
空间复杂度：O(n), 开辟了一个辅助栈。