遇到的错误和解决方案：
1.函数嵌套函数
2. 调用函数返没有返回值 return
3.函数调用函数中间的参数的传递和全局变量和局部变量的问题
解决：函数的闭包问题
闭：指的是定义在函数内部的函数
注意：作用域关系在函数定义阶段就规定死了，与调用位置无关
闭包函数：定义在函数内部的函数，并且该函数包含对外部函数作用域中名字的引用，该函数就称为闭包函数
闭包的意义：返回的函数对象，不仅仅是一个函数对象，在该函数外还包裹了一层作用域，这使得，该函数无论在何处调用，优先使用自己外层包裹的作用域
函数嵌套与闭包函数 - 鲁之敬 - 博客园 (cnblogs.com)
Python闭包函数的使用和原理 - 腾讯云开发者社区-腾讯云 (tencent.com)
def first():
res = []
def second():
res.append(1)
second()
print( res)
first()
#means
def first():
res = []
def second():
res.append(1)
second()
return res
x = first()
print(x)#第六题
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
#
class Solution:
def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
# write code here
res = []
if not listNode:
print(3)
return res
def traverse(root):
if not root:
return res
# if root.next == None:
# res.append(root.val)
# print(2,res)
# return res //注意：在函数中如果用了上一层函数的变量，nonlocal类型的变量，那就是直接对上一层函数的进行修改，不能用return ,不然只能得到空
if root.next:
traverse(root.next)
res.append(root.val)
print(1,res)
traverse(listNode)
return res //在最后直接输出就好，不用从上面使用 res=traverse(listNode)获得
4.调用函数
不带括号：只是赋值而没有启动函数
带括号：赋值并且函数
def bar():
print('from bar')
f = bar()
# from bar
def bar():
print('from bar')
f = bar
f()
# from bar
def bar():
print('from bar')
f = bar
# 没有输出
带传参
5.TypeError: descriptor 'append' for 'list' objects doesn't apply to a 'int' object
并没有看明白这是啥问题
题目：
五：替换空格： 从后向前看，从末尾一开始计算好要移动的位置
六：从尾到头打印 ：
1.利用栈分析 从头到尾把数据加入到栈中，再利用pop输出元素
2.利用递归写
递归类似与栈，栈的深度是一定的，如果数据很多就会超过栈的深度
七：做题老是会遇到一种情况，要保留第一次循环的结果，比如第七题，需要保留root的内容最后输出，（或者构建出树之后在从后往前输出？）
~~~怎么处理每一个节点
~~~怎么处理叶子节点~~
一开始
class Solution:
def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
# write code here
#在pre中找到根节点，然后在vin中根据根节点分成左右子树的vin，再根据分成的左右子树
# 的长度去pre中找同样长度的pre内容
if len(pre) ==0:
return
# if len(pre) == 1 and len(vin) == 1:
# return
root = TreeNode(pre[0])
print(root.val)
# 输出 1 2 3 然后就停止了，证明是遇到第一个叶子节点的时候返回出错
# print(root.val)
root_vinindex = vin.index(pre[0])
# 求左右子树的vin
leftvin = vin[:root_vinindex]
rightvin = vin[root_vinindex+1:]
# 求左右子树的长度
left_length=len(leftvin)
right_length = len(rightvin)
# 求左右子树的pre
leftpre = pre[1:left_length+1]
rightpre = pre[left_length+1:]
print(1,leftpre,2,rightpre)
print(1.1,leftvin,2.2,rightvin)
root.left = TreeNode(leftpre[0])
root.right = TreeNode(rightpre[0])
if len(leftpre)>0:
self.reConstructBinaryTree(leftpre,leftvin)
if len(rightpre)>0:
self.reConstructBinaryTree(rightpre,rightvin)
return root首先，原本的思路算不出来，但是通过加一个队列，使用层次遍历的方法，每个节点构建字典，对应它自己的前序和中序，最后读取字典，利用层次遍历一层一层的加左右节点，也许能解决？感觉很麻烦
因为列表长度问题，一个列表如果只有list[0]但是你调用了list[1]就会溢出
我不知道怎么来处理这个最后list[0]的 的情况，然后看了大佬的代码，通过直接
root.left = createfunction()构建函数来解决
再通过if not root :return 来限制叶子节点之下的节点，咱就是说这也太牛了吧wwww
换个思路解决问题
class Solution:
def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
# write code here
#在pre中找到根节点，然后在vin中根据根节点分成左右子树的vin，再根据分成的左右子树
# 的长度去pre中找同样长度的pre内容
if not pre:
return
# if len(pre) == 1 and len(vin) == 1:
# return
root = TreeNode(pre[0])
print(root.val)
# 输出 1 2 3 然后就停止了，证明是遇到第一个叶子节点的时候返回出错
# print(root.val)
root_vinindex = vin.index(pre[0])
# 求左右子树的vin
leftvin = vin[:root_vinindex]
rightvin = vin[root_vinindex+1:]
# 求左右子树的长度
left_length=len(leftvin)
right_length = len(rightvin)
# 求左右子树的pre
leftpre = pre[1:left_length+1]
rightpre = pre[left_length+1:]
# print(1,leftpre,2,rightpre)
# print(1.1,leftvin,2.2,rightvin)
# ！！！这一步很厉害哇我靠，通过return 和 直接调用函数的方法构造树
root.left = self.reConstructBinaryTree(leftpre,leftvin)
root.right = self.reConstructBinaryTree(rightpre,rightvin)
return root
细想，我的代码和和正确代码最大的区别是
我的代码使用root.left = TreeNode (从子节点前序列表取值构建），是一种从上到下的思想，从上往下把左右节点加到root上
而修改后的代码，是使用递归从下到上的思想，从到达叶子节点的return 开始构建，从下到上 第一层：把叶子节点左右左右节点加到上一层节点，之后的每一层把左右子树加到root节点
发散：在斐波那契数列中也有类似的思想，一开始是从上到下构建数列，然后 第一次修改 利用备忘录记录下可能重读计算的节点，之后再使用到节点的值，第二次修改时想要计算f(n)的斐波那契数列，从下往上计算 f(1)-f(2)---f(n)的方式计算。
发现自己缺：
1.返回值处理的不好
2.循环，递归结束位置处理的不好
第八题：求二叉树的下一个节点
注意：在输入中，看似输入了一个集合和一个Int数字，实则输入一个二叉树和一个节点，只需要直接对节点操作就行，某些时候看似多种情况，列出来还要记得找规律，结合中序遍历的特点
# -*- coding:utf-8 -*-
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
def GetNext(self, pNode):
# write code here
#思想：在自己找到临界值节点做尝试，找到合适的节点，用实例来找下一个节点
# 选择几个特殊节点：8 -- 9 （有右子树 -- 右子树的最左子节点） 6-7 10-11
# 5 -- 6 （没有右子树，且为父节点的左子节点 -- 头节点） self.next 9-10
# 7 -- 8 （没有右子树，且为父节点的右子节点 -- 某一级父节点是左子节点）
# 11 -- null 树的最右叶子节点 以上三种情况都不是
# 也就是分为 ：有右子树 --- 右子树最左节点
# 没有右子树 --- 是父节点的左子节点 --父节点
# 是父节点的右子节点 --找父节点（是左子节点）
if pNode == None:
return None
# 第二步，找每个节点有什么特殊的地方 ，从节点本身的三个指针来看
pNext = None
if pNode.right:
pcurrent = pNode.right
while pcurrent.left:
pcurrent = pcurrent.left
pNext = pcurrent
elif pNode.next:
pcurrent = pNode
pParent = pNode.next
while pParent!=None and pcurrent == pParent.right:
# 如果是右子节点，则进入循环，这个地方相当于把两个情况合并，最终都是要找某个父节点
pcurrent = pParent
pParent = pParent.next
pNext = pParent
return pNext
第九题：用两个栈实现队列
咱就是说，看不懂输入输出怎么解
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
# write code here
def pop(self):
# return xx
if len(self.stack2)>0:
return self.stack2.pop()
else:
while len(self.stack1)>0:
self.stack2.append(self.stack1.pop())
return self.pop()第十题：斐波那契数列
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
def Fibonacci(self , n: int) -> int:
res = 0
# write code here
a = 1
b = 1
for i in range(n+1):
if i== 1 or i==2:
a = 1
b = 1
c = 1
else:
c = a+b
a = b
b = c
return c
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
def Fibonacci(self , n: int) -> int:
f = [False for _ in range(n+1)]
# write code here
for i in range(n+1):
if i ==1 or i==2:
f[i] = 1
else:
f[i] = f[i-1] + f[i-2]
return f[n]
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
def Fibonacci(self , n: int) -> int:
# write code here
if n ==1 or n==2:
return 1
else:
return self.Fibonacci(n-1)+self.Fibonacci(n-2)
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
def Fibonacci(self , n: int) -> int:
# write code here
f = [False for _ in range(n+1)]
def help(f,n):
if n ==1 or n == 2:
f[n] = 1
if f[n]!=False:
return f[n]
else:
f[n] =help(f,n-1)+help(f,n-2)
return f[n]
res = help(f,n)
return res
第十一题：旋转数组
class Solution:
def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
# write code here
for i in range(len(rotateArray)-1):
if rotateArray[i]>rotateArray[i+1]:
return rotateArray[i+1]
return rotateArray[0]#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param rotateArray int整型一维数组
# @return int整型
#
class Solution:
def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
# write code here
maxya = len(rotateArray)-1
minya = 0
def cut(a,b):
if a==b-1:
# 考虑 顺序队列情况 【1，4】
if rotateArray[a]<rotateArray[b]:
print(b)
return rotateArray[a]
else:
print(a)
return rotateArray[b]
avg = int((a+b)/2)
print(a,b,avg)
if rotateArray[avg] > rotateArray[b]:
a=avg
elif rotateArray[avg] < rotateArray[b]:
b=avg
else:
# 考虑重复数字情况 [2,2,2,2,1,2]
for i in range((len(rotateArray)-1)):
if rotateArray[i]>rotateArray[i+1]:
return rotateArray[i+1]
# 考虑顺序[1,2,3,4,5]
return rotateArray[0]
return cut(a,b)
res = cut(minya,maxya)
# print(res)
return res
第十二题：矩阵中的路径
三个变量 word_index,col,row
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix char字符型二维数组
# @param word string字符串
# @return bool布尔型
#
class Solution:
def hasPath(self , matrix: List[List[str]], word: str) -> bool:
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
if len(word) > len(matrix)*len(matrix[0]):
return False
# write code here
rows = len(matrix)
cols = len(matrix[0])
visit = [[False]*cols for _ in range(rows)]
# print(visit)
# 这个函数含义是：从matrix[rol][col]=word[index --len(word)]
# [[A]],"B"
def arround(matrix,word,visit,index_word,row,col):
nonlocal rows,cols
if index_word == len(word):
return True
path_index = False
# print('index',index_word,word[index_word],matrix[row][col])
if row < rows and row >= 0 and col>=0 and col<cols and matrix[row][col] == word[index_word] and not visit[row][col]:
index_word+=1
visit[row][col] = True
# 下面这一步运用递归直接查找到最后一个数，最后的payh_index是反复验证之后确定能走到最后的
path_index = arround(matrix,word,visit,index_word,row,col-1) or arround(matrix,word,visit,index_word,row,col+1) or arround(matrix,word,visit,index_word,row+1,col) or arround(matrix,word,visit,index_word,row-1,col)
if not path_index:
index_word-=1
visit[row][col] = False
return path_index
index_word = 0
for i in range(rows):
for j in range(cols):
print(i,j)
if arround(matrix,word,visit,index_word,i,j):
return True
return False
#
第十三题：机器人的运动范围
只能过1/2的用例，
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param threshold int整型
# @param rows int整型
# @param cols int整型
# @return int整型
#
class Solution:
def movingCount(self , threshold: int, rows: int, cols: int) -> int:
# write code here
def checkrc(row:int,col:int):
res =0
print('in',row,col)
while row!=0:
num = row%10
row = int(row/10)
# print('row',num,row)
res += num
# list.append(num)
while col!=0:
num = col%10
col = int(col/10)
# print('col',num,col)
res += num
# list.append(num)
# res = 0
# for i in listall:
# res += i
# print('res',res)
print('out',res)
return res
allnum = 0
listtmp =[0]
for row in range(rows):
for col in range(cols):
temp = checkrc(row,col)
if temp>threshold:
break
allnum+=1
localtmp = [list([row,col])]
listtmp.append(localtmp)
print(listtmp)
return allnum
这个结果很意外，以为会多，结果少了，没想通在哪少了
以为会多的原因是：他要求上下左右遍历，但是我是全遍历，按理说不应该，下周来想吧，想不动了好累
第十四题：减绳子
分成两段，n<=3一段 ，n>3另一段 因为n<=3无规律，n>3有规律
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
def cutRope(self , n: int) -> int:
# write code here
# 思想：剪成n段，一刀一刀的想， n 减一刀 减成长度为 i 和 n-i的长度，
# f[n] = f[i] * f[n-i] (0<i<n) 所以利用从下往上的思想
if n<2:
return 0
if n==2:
return
if n==3:
return 2
f=[False]*(n+1)
# 当n>3时，4--2，2 5--2，3 6--3，3
f[1] = 1
f[2] = 2
f[3] = 3
for i in range(5,n+1):
maxtmp = 0
for j in range(1,i):
tmp = f[j]*f[i-j]
if maxtmp<tmp:
print('li',i,j,i-j,tmp)
maxtmp = tmp
f[i] = maxtmp
print(f)
return f[n]
第十六题：数值的次方
class Solution:
def Power(self , base: float, exponent: int) -> float:
# write code here
# 特殊情况：1. base = 0 return 0
# 2. base != 0 exponent = 0 return 1
# 3. base < 0 exponent为偶数，则结果为正 ，否则结果为负
# 4. exponent < 0 1/base 的abs(exponent次方)
signer = 1
# 符号位
if base == 0:
return 0
if exponent == 0:
return 1
if exponent<0:
base = 1/base
exponent = -exponent
if base < 0:
if exponent%2 != 0:
print('负数')
signer = -1
res = base
for i in range(exponent-1):
res = res * base
print(res , signer)
# res = signer * res
return res
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param base double浮点型
# @param exponent int整型
# @return double浮点型
#
class Solution:
def Power(self , base: float, exponent: int) -> float:
# write code here
# 特殊情况：1. base = 0 return 0
# 2. base != 0 exponent = 0 return 1
# 3. base < 0 exponent为偶数，则结果为正 ，否则结果为负
# 4. exponent < 0 1/base 的abs(exponent次方)
if base == 0:
return 0
if exponent == 0:
return 1
if exponent<0:
base = 1/base
exponent = -exponent
f = [False]*(exponent+1)
f[0] = 1
f[1] = base
def traverse(base,n:int):
# 减少复杂度的思想
# f(n) = f(n/2)*f(n/2) 若n 为偶数
# f(n) = f(n-1/2)*f(n-1/2)*f(1) 若n为奇数
print(n)
nonlocal f
print(f)
if f[n]!=False:
return f[n]
if n%2 == 0:
print(n,'偶数')
return traverse(base,int(n/2))*traverse(base,int(n/2))
else:
print(n,'奇数')
return traverse(base,int((n-1)/2))*traverse(base,int((n-1)/2))*f[1]
res = traverse(base,exponent)
return res
咱就是说 运行时间怎么还变长了
第17题：打印从1到最大的n位数
#
class Solution:
def printNumbers(self , n: int) -> List[int]:
# write code here
res = 1
list1 = []
for i in range(n):
res = res *10
for j in range(1,res):
list1.append(j)
return list1第18题 删除链表节点
#
class Solution:
def deleteNode(self , head: ListNode, val: int) -> ListNode:
# write code here
if not head or val is None:
return None
if head.val == val:
return head.next
headconst = head
prev = head
node = head.next
while node:
# print(node.val)
if node.val == val:
prev.next = node.next
node.next = None
del node
return head
else:
prev = node
node = node.next
return None第21题：调整数组顺序，使得奇数位于偶数之前
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param array int整型一维数组
# @return int整型一维数组
#
class Solution:
def reOrderArray(self , array: List[int]) -> List[int]:
# write code here
if len(array) <= 1:
return array
start = 0
end = len(array) - 1
while start < end:
while array[start] %2 ==1 and start<end:
start += 1
while array[end] %2 ==0 and end >start:
end -= 1
temp = array[start]
array[start] = array[end]
array[end] = temp
return array
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param array int整型一维数组
# @return int整型一维数组
#
class Solution:
def reOrderArray(self , array: List[int]) -> List[int]:
# write code here
if len(array)<=0:
return []
res1 = []
res2 = []
for i in range(len(array)):
if array[i] % 2 ==1:
res1.append(array[i])
else:
res2.append(array[i])
res1.extend(res2)
return res1
第22题，链表中倒数第k个节点
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pHead ListNode类
# @param k int整型
# @return ListNode类
#
class Solution:
def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
# write code here
if not pHead or k<=0:
return None
firstnode = pHead
i = k-1
j = 0
while j<i:
firstnode = firstnode.next
j+=1
if not firstnode:
return None
while firstnode.next:
pHead = pHead.next
firstnode = firstnode.next
return pHead思考：在处理链表时，由于链表计数和定位不像数组方便，因此可以使用两个指针解决问题
eg:
1.寻找链表的中间节点，定义start和end同时指向第一个节点，但是end的速度是start的两倍
while end != None:
start =start.next
end =end.next
if end != None:
end = end.next
else:
return start 2.寻找链表中是否有环，一个在前，一个在后，能遇到则有环，前后差为环内节点数
第23题：链表中环的入口结点
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if not pHead:
return None
# 查看是否有环，以及找到一个环内的点
def meet(pHead):
pslow = pHead.next
if not pslow:
return None
pfast = pslow.next
# 由于有两个指针，如果有环，且两个指针移动的速度不同，则两个指针一定会相遇
while pfast and pslow:
if pfast == pslow:
return pfast
pslow = pslow.next
pfast = pfast.next
if pfast:
pfast = pfast.next
return pfast
# pfast一定是环内的点
# 找到环内的点后，确定环内一共有几个节点
def countnode(pnode):
if pnode.next == pnode:
return 1
pconst = pnode
pmove = pnode.next
countnode = 1
while pmove != pconst:
pmove = pmove.next
countnode += 1
return countnode
# 确定环内节点后，在找到起点
def findnode(n,pHead):
pfast = pHead
pslow = pHead
for i in range(n):
pfast = pfast.next
while pfast != pslow:
pfast = pfast.next
pslow = pslow.next
return pslow
constHead = pHead
pNode = meet(pHead)
if not pNode:
return None
n = countnode(pNode)
penter = findnode(n,constHead)
return penter
第25题：合并两个有序列表
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
#
class Solution:
def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
if not pHead1:
return pHead2
if not pHead2:
return pHead1
pHead = None
# 如果要使用递归，要从上往下分析和从下往上组合
if pHead1.val < pHead2.val:
pHead = pHead1
pHead.next = self.Merge(pHead1.next,pHead2)
else:
pHead = pHead2
pHead.next = self.Merge(pHead1,pHead2.next)
return pHead
在使用递归的时候，例如本题，利用self.next = self.merge(参数1，参数2)；
先是一种从上往下的思想
每个节点的next = 剩余两个两链表中节点链表合并
其次 ，剩余两链表合并是通过对比大小，选出一个节点，再以这个节点为头节点来，来选择后一个节点
自身调用：解决 return 单个节点的问题，这种传递不通过return ,return 只是帮助寻找最后一个节点，传递通过self .next =self.函数（参数1，参数2）
起始条件： 找头节点
终止条件：节点为空
动态变化：参数1 和 参数2
被动变化：self.next
行动：比较两个链表头节点，把较大的头节点和前面的链表结合起来，合并之后，再找两个链表的头节点，比较大小，与刚才合并的尾节点连接------对变化的两个链表和尾节点做重复的动作（递归），并且动作导致链表和尾节点的变化 --- 递归结合在self.next，导致变化。
第26题，树的子结构
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot1 TreeNode类
# @param pRoot2 TreeNode类
# @return bool布尔型
#
class Solution:
def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
# write code here
# 两步：1.找到B树的头节点 2.从头节点开始验证是不是子结构
if not pRoot1 or not pRoot2:
return False
def does(pRoot1,pRoot2):
# 深入进取，到达叶子节点，则返回叶子节点的对
# if pRoot1 and pRoot2:
# print('does',pRoot1.val,pRoot2.val)
if not pRoot2:
return True
if pRoot1.val != pRoot2.val:
return False
if not pRoot1:
return False
return does(pRoot1.left,pRoot2.left) and does(pRoot1.right,pRoot2.right)
def findtool(pRoot1,pRoot2):
res = False
if pRoot1 and pRoot2 :
# print('find',pRoot1.val,pRoot2.val)
if pRoot1.val == pRoot2.val:
res = does(pRoot1,pRoot2)
# print(res)
if not res:
res = findtool(pRoot1.left,pRoot2)
if not res:
res = findtool(pRoot1.right,pRoot2)
return res
return findtool(pRoot1,pRoot2)
改正 想清楚顺序 想清楚其他的
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot1 TreeNode类
# @param pRoot2 TreeNode类
# @return bool布尔型
#
class Solution:
def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
# write code here
# 两步：1.找到B树的头节点 2.从头节点开始验证是不是子结构
if not pRoot1 or not pRoot2:
return False
def does(pRoot1,pRoot2):
# 深入进取，到达叶子节点，则返回叶子节点的对
if pRoot1 and pRoot2:
print('does',pRoot1.val,pRoot2.val)
if not pRoot2:
return True
if not pRoot1:
return False
if pRoot1.val != pRoot2.val:
return False
return does(pRoot1.left,pRoot2.left) and does(pRoot1.right,pRoot2.right)
def findtool(pRoot1,pRoot2):
res = False
if pRoot1 and pRoot2 :
print('find',pRoot1.val,pRoot2.val)
if pRoot1.val == pRoot2.val:
res = does(pRoot1,pRoot2)
print(res)
if not res:
res = findtool(pRoot1.left,pRoot2)
if not res:
res = findtool(pRoot1.right,pRoot2)
return res
return findtool(pRoot1,pRoot2)
第28题：二叉树的镜像
任何二叉树都必须考虑 根节点 左子节点，右子节点
在操作前进行判断，操作是对那一部分进行修改，需不需要和前面连接起来
如果需要连接起来则是 self.next = 函数（参数1， 参数2）
如果不需要连接 则 函数（左子节点） 函数（右子节点）
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return TreeNode类
#
class Solution:
def Mirror(self , pRoot: TreeNode) -> TreeNode:
# write code here
if not pRoot:
return None
if not pRoot.left and not pRoot.right:
return pRoot
temp = pRoot.left
pRoot.left = pRoot.right
pRoot.right = temp
# 判断+修改 如果存在 则对左节点操作
if pRoot.left:
self.Mirror(pRoot.left)
# 如果存在 则对右节点操作
if pRoot.right:
self.Mirror(pRoot.right)
return pRoot第29题 ，对称二叉树
思路：
对于根节点 不用考虑
对于第一层的左右子树 把他看成两颗树 判断两棵树是不是对称的
1.根节点的值是不是相同的
2.根节点左子树是不是和 根节点的右子树 对称
3.对称的条件 ： 左子树的左和右子树的右对称，左子树的右和右子树的左对称，直到两边都到了叶子节点
三个终止条件：
- 同时到叶子节点，返回True
- 不同时到叶子节点，返回False
- 从根节点到叶子节点，对称节点的val不相等，返回False
- 否则，继续判断 左子树的左和右子树的右对称 and 左子树的右和右子树的左对称（递归）
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return bool布尔型
#
class Solution:
def isSymmetrical(self , pRoot: TreeNode) -> bool:
# write code here
# 对称二叉树 判断左子树的左右 和 右子树的右左 是不是一样的
if not pRoot:
return True
# 因为要判断左子树和右子树，所以定义一个函数 输入为两颗子树
def pbool(pRoot1,pRoot2):
# 如果都有左右子树 且该节点的值相等，则递归判断左子树的左和右子树的右，左子树的右和右子树的左
if not pRoot1 and not pRoot2:
return True
# 叶子节点
if not pRoot1 or not pRoot2:
return False
# 某个子树到叶子但另一个还没到
if pRoot1.val != pRoot2.val:
return False
# 值不等
# 排除完三种情况之后，剩下的就是都有左右子树，且根节点值相同
res_wai = pbool(pRoot1.left,pRoot2.right)
res_nei = pbool(pRoot1.right,pRoot2.left)
res = res_nei and res_wai
return res
res = pbool(pRoot,pRoot)
return res第30题，包含min栈的函数
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.stack_min = []
self.minval = 10000
def push(self, node):
# write code here
self.stack.append(node)
if node < self.minval:
self.minval = node
self.stack_min.append(self.minval)
def pop(self):
# write code here
self.stack.pop()
self.stack_min.pop()
self.minval = self.stack_min[-1]
return
def top(self):
# write code here
return self.stack[-1]
def min(self):
# write code here
return self.stack_min[-1]
或者
注意：minval在Push 和 Pop的时候都要改变
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.stack_min = []
def push(self, node):
# write code here
self.stack.append(node)
if not self.stack_min:
self.stack_min.append(node)
if node < self.stack_min[-1]:
self.stack_min.append(node)
else:
self.stack_min.append(self.stack_min[-1])
def pop(self):
# write code here
print('pop before',self.stack,self.stack_min)
self.stack.pop()
self.stack_min.pop()
print('pop',self.stack,self.stack_min)
return
def top(self):
# write code here
return self.stack[-1]
def min(self):
# write code here
return self.stack_min[-1]
第31题 。栈的压入和弹出
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pushV int整型一维数组
# @param popV int整型一维数组
# @return bool布尔型
#
class Solution:
def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
# write code here
if not pushV and not popV:
return True
push_ed = []
start = 0
while start < len(popV):
# 当popV[start] ！= push_ed[-1] 时，那继续往后找，直到找到，start+=1 push_ed.pop()
# if not pushV and not push_ed:
# return False
if not push_ed:
push_ed.append(pushV[0])
pushV.pop(0)
if push_ed[-1] != popV[start]:
if not pushV:
return False
push_ed.append(pushV[0])
pushV.pop(0)
else:
push_ed.pop()
start += 1
if start == len(popV):
return True
else:
return False
第32题 。从上到下打印二叉树 因该用队列 ，而不是栈 ，命名有错
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型一维数组
#
class Solution:
def PrintFromTopToBottom(self , root: TreeNode) -> List[int]:
# write code here
if not root:
return None
res = []
temp_stack = [root]
while temp_stack:
# 注意这一行，同时对stack取数和删除top节点
temp_node = temp_stack.pop(0)
res.append(temp_node.val)
if temp_node.left:
temp_stack.append(temp_node.left)
if temp_node.right:
temp_stack.append(temp_node.right)
return res
二叉树的后续遍历
我靠！！！到底错在哪了 我要吐了
想死 打错了一个字母检查了半小时
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param sequence int整型一维数组
# @return bool布尔型
#
class Solution:
def VerifySquenceOfBST(self , sequence: List[int]) -> bool:
# write code here
if not sequence:
return False
# 判断后续遍历要用递归 先根据根节点判断出左右子树的数组，再判断左右子树的数组是不是后序遍历
# 先判断一个试试看
root = sequence[-1]
for i in range(len(sequence)):
if sequence[i]>root:
break
left_s = sequence[0:i]
right_s = sequence[i:-1]
# print(left_s,right_s)
# for i in left_s:
# if i>=root:
# return False
for i in right_s:
if i <= root:
return False
print(root,left_s,right_s)
res_l = True
res_s = True
if left_s:
res_l = self.VerifySquenceOfBST(left_s)
if right_s:
print(right_s)
res_s = self.VerifySquenceOfBST(right_s)
res = res_l and res_s
return res
第34题：找路径
又是有问题得代码 但是我找不到问题在哪，我吐了
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @param target int整型
# @return int整型二维数组
#
class Solution:
def FindPath(self , root: TreeNode, target: int) -> List[List[int]]:
# write code here
if not root or not target:
return None
list_all = []
list_temp = []
temp_target = 0
def traverse(root,temp_target,target):
# nonlocal list_all
if not root:
return
temp_target += root.val
list_temp.append(root.val)
print(root.val)
if temp_target == target and not root.left and not root.right:
# list_all.append(list_temp) 赋值
# list_all.append(list_temp[:]) 浅拷贝1
list_all.append(list(list_temp))
# 浅拷贝2
# list_all.append(copy.copy(list_temp)) 浅拷贝3
print('temp',list_temp)
print(id(list_temp))
print('list_all',list_all)
print(id(list_all[0]))
if root.left:
traverse(root.left,temp_target,target)
if root.right:
traverse(root.right,temp_target,target)
print('before',list_temp,temp_target)
temp_target -= root.val
list_temp.remove(root.val)
print('after',list_temp,temp_target)
traverse(root,temp_target,target)
return list_all
第35题：复杂链表的复制
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return pHead
ran_dict = {}
# pHead1 = pHead 赋值操作，指向同一个位置
pHead1 = RandomListNode(pHead.label)
pHead1_const = pHead1
while pHead.next:
pHead1_next = RandomListNode(pHead.next.label)
pHead1.next = pHead1_next
if pHead.random:
pHead1_random = RandomListNode(pHead.random.label)
pHead1.random = pHead1_random
# ran_dict[pHead] = pHead.random
pHead1 = pHead1.next
pHead = pHead.next
# print(ran_dict)
return pHead1_const
第36题，二叉搜索树变成双向列表
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
#
# @param pRootOfTree TreeNode类
# @return TreeNode类
#
class Solution:
head = None
pre = None
def Convert(self , pRootOfTree ):
# write code here
if not pRootOfTree:
return
self.Convert(pRootOfTree.left)
if not self.head:
self.head = pRootOfTree
self.pre = pRootOfTree
else:
self.pre.right = pRootOfTree
pRootOfTree.left = self.pre
self.pre = pRootOfTree
self.Convert(pRootOfTree.right)
return self.head
本文含有隐藏内容，请 开通VIP 后查看