剑指offer（四）
剑指offer（16-20）。
合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，
当然我们需要合成后的链表满足单调不减规则。
思路
- 递归
- 非递归
代码实现
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
#递归方法
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
list_merge=None #构建一个新的链表存储合并后的链表
if pHead1==None: #一个为空就返回另外一个链表
return pHead2
if pHead2==None:
return pHead1
if pHead1.val<=pHead2.val:
list_merge=pHead1
list_merge.next=self.Merge(pHead1.next,pHead2)
else:
list_merge=pHead2
list_merge.next=self.Merge(pHead1,pHead2.next)
return list_merge
#非递归方法
class Solution2:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
head=ListNode(90)
p=head
if pHead1==None:
return pHead2
if pHead2==None:
return pHead1
while pHead1 and pHead2:
if pHead1.val<=pHead2.val:
head.next=pHead1
pHead1=pHead1.next
else:
head.next=pHead2
pHead2=pHead2.next
head=head.next #后移，方便链接下一次循环中选取的结点
if pHead1: #pHead1和pHead2一个为空，将其链接到合并后的链表中
head.next=pHead1
if pHead2:
head.next=pHead2
return p.next
树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路
- 递归
代码实现
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
result=False
if pRoot1!=None and pRoot2!=None: #当Tree1和Tree2都不为空时比较，否则直接返回False
if pRoot1.val==pRoot2.val: #如果找到了对应Tree2根节点的点
result=self.doesTree1haveTree2(pRoot1,pRoot2) #以这个根节点为起点判断是否包含Tree2
if not result:
result=self.HasSubtree(pRoot1.left,pRoot2) #如果没找到，去root左儿子当作起点，递归判断是否包含Tree2
if not result:
result=self.HasSubtree(pRoot1.right,pRoot2) #如果没找到，去root右儿子当作起点，递归判断是否包含Tree2
return result
def doesTree1haveTree2(self,node1,node2):
if node2==None: #如果Tree2已经遍历完了都能对上，返回True
return True
if node1==None: #如果Tree2还没遍历完，Tree1却遍历完了，返回False
return False
if node1.val!=node2.val: #其中只要有一个节点没对上，返回False
return False
#如果根节点对应的上，再分别去子节点里匹配
return self.doesTree1haveTree2(node1.left,node2.left) and self.doesTree1haveTree2(node1.right,node2.right)
二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
二叉树的镜像定义：源二叉树
8
/
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ /
11 9 7 5
思路
- 递归
- 非递归，借用一个栈或者队列
代码实现
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
#方法一，递归
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
if root==None:
return None
if root:
root.left,root.right=root.right,root.left #翻转根节点的左右孩子结点
if root.left!=None: #递归翻转左子树
self.Mirror(root.left)
if root.right!=None: #递归翻转右子树
self.Mirror(root.right)
return root
#方法二，非递归，借用一个栈实现（其实借用一个队列也可以，思路是一样的）
class Solution2:
# 返回镜像树的根节点
def Mirror(self, root):
if root==None:
return None
result=[] #创建一个空栈
result.append(root)
while result:
tree=result[-1] #取栈顶元素
result.pop(-1) #栈顶元素出栈
if (tree.left!=None or tree.right!=None): #交换结点的左右孩子
tree.left,tree.right=tree.right,tree.left
if tree.left: #左孩子入栈
result.append(tree.left)
if tree.right:
result.append(tree.right) #右孩子入栈
return root
顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：
1 2 3 4 输出：1,2,3,4,8,12,16,15 14,13,9,5,6,7,11,10.
5 6 7 8
9 10 11 12
13 14 15 16
思路
-
可以模拟魔方逆时针旋转的方法，一直做取出第一行的操作
例如
1 2 3
4 5 6
7 8 9
输出并删除第一行后，再进行一次逆时针旋转，就变成：
6 9
5 8
4 7
继续重复上述操作即 -
按照矩阵最上一行、最右一列，最下一行和最左一列分别处理
代码实现
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
result=[] #最终顺时针读取完成后的列表
while matrix:
result+=matrix.pop(0) #循环取出矩阵第一行
if not matrix or not matrix[0]: #矩阵是否为空，个人感觉matrix[0]这个判断没有必要
break
matrix=self.turn(matrix) #逆时针旋转矩阵
return result
def turn(self,matrix):
rows=len(matrix) #矩阵的行数
cols=len(matrix[0]) #矩阵列数
new_matrix=[] #最终逆时针旋转后的矩阵
for i in range(cols):
new_matrix_cut=[] #存储每一次循环时，每一列的矩阵值
for j in range(rows):
new_matrix_cut.append(matrix[j][i])
new_matrix.append(new_matrix_cut) #每一列读取完后，附加到总的矩阵列表
new_matrix.reverse() #列表中的矩阵反转
return new_matrix
#方法二
class Solution2:
def printMatrix(self, matrix):
res = [] #最终顺时针读取完成后的列表
while matrix:
res += matrix.pop(0) #从前向后读取最上面的一行数据
if matrix and matrix[0]:
for row in matrix: #读取最右边的一列（即每一行的最后一个数据）
res.append(row.pop())
if matrix: #从后向前读取最下边的一行
res += matrix.pop()[::-1]
if matrix and matrix[0]: # 读取最左边一列的数据（即每一行的第一个数据）
for row in matrix[::-1]:
res.append(row.pop(0))
return res
包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到
栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路
- 设置一个辅助栈来存储最小的元素
代码实现
class Solution:
def __init__(self):
self.stack=[] #主栈
self.min_stack=[] #辅助栈，存储最小的元素
def push(self, node): #入栈
self.stack.append(node) #新元素入主栈
if not self.min_stack or node<self.min_stack[-1]: #如果辅助栈为空或者新元素比辅助栈顶元素小，新元素也入辅助栈
self.min_stack.append(node)
def pop(self): #出栈
if self.min_stack[-1]==self.stack[-1]: #如果辅助栈顶元素和主栈顶元素相同，辅助栈顶元素出栈
self.min_stack.pop()
self.stack.pop() #主栈顶元素出栈
def top(self): #返回栈顶元素
return self.stack[-1]
def min(self): #最小值为辅助栈顶元素值
return self.min_stack[-1]
