结语：
也算是刷完了这套题，很是惭愧，其中关于二叉树部分和运用递归部分的问题多有参考别人高赞答案的思路。不过这也算是发现了问题，之后继续努力。
56. 删除链表中重复的结点
又可以当词频统计……
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
pres = []
res = []
while pHead:
pres.append(pHead.val)
pHead = pHead.next
for i in pres:
if pres.count(i) == 1:
res.append(i)
pre = dummy = ListNode(0)
for i in res:
node = ListNode(i)
pre.next = node
pre = pre.next
return dummy.next
57. 二叉树的下一个结点
如果该节点有右子树，返回该右子树的最左叶子节点，如果没有右子树，则看它的父节点是不是祖父结点的左结点，如果是则返回祖父节点，如果不是则上溯祖父节点的父节点……直到找到祖先结点是左子树的结点，如果找不到则返回None
# -*- 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
if not pNode:
return pNode
if pNode.right:
left=pNode.right
while left.left:
left=left.left
return left
while pNode.next:
if pNode.next.left==pNode:
return pNode.next
pNode=pNode.next
58. 对称的二叉树
对称的意思就是左子树的左边等于右子树的右边and左子树的右边等于右子树的左边
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetrical(self, pRoot):
# write code here
def is_same(p1,p2):
if not p1 and not p2:
return True
if (p1 and p2) and p1.val==p2.val:
return is_same(p1.left,p2.right) and is_same(p1.right,p2.left)
return False
if not pRoot:
return True
if pRoot.left and not pRoot.right:
return False
if not pRoot.left and pRoot.right:
return False
return is_same(pRoot.left,pRoot.right)
59. 按之字形顺序打印二叉树
牛客网太坑了给的函数名是isSymmetrical但判题是调用的是Print
class Solution:
def __init__(self):
self.an = []
`isSymmetrical`#给的函数名有问题
def Print(self, pRoot):
# write code here
if pRoot == None:
return []
return self.h([pRoot], False)
def h(self, a, flag):
if a == []:
return self.an
b, c = [], []
for i in a:
b.append(i.val)
if i.left:
c.append(i.left)
if i.right:
c.append(i.right)
if flag:
b.reverse()
self.an.append(b)
return self.h(c, ~flag)
60. 把二叉树打印成多行
和上一题同样的解法
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.an = []
def Print(self, pRoot):
# write code here
if pRoot == None:
return []
return self.h([pRoot])
def h(self, a):
if a == []:
return self.an
b, c = [], []
for i in a:
b.append(i.val)
if i.left:
c.append(i.left)
if i.right:
c.append(i.right)
self.an.append(b)
return self.h(c)
61. 序列化二叉树
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Serialize(self, root):
if not root:
return '#'
res = str(root.val)
res += '_' + self.Serialize(root.left)
res += '_' + self.Serialize(root.right)
return res
# write code here
def Deserialize(self, s):
lst = s.split('_')
def des():
if not lst:
return None
v = lst.pop(0)
if v == '#':
return None
else:
head = TreeNode(int(v))
head.left = des()
head.right = des()
return head
return des()
62. 二叉搜索树的第K小个结点
中序遍历取第K个值
class Solution:
# 返回对应节点TreeNode
def KthNode(self, pRoot, k):
# write code here
if not pRoot or k<1:
return None
buf=[]
if len(self.inorder(pRoot,buf))<k:
return None
return self.inorder(pRoot,buf)[k-1]
def inorder(self,pRoot,buf):
if not pRoot:
return None
self.inorder(pRoot.left,buf)
buf.append(pRoot)
self.inorder(pRoot.right,buf)
return buf
63. 数据流中的中位数
牛客网给的def GetMedian(self):但是判题的时候会多一个参数def GetMedian(self,n):
以及 偷懒了 ヘ( _ . _ヘ)
直接用sort()方法排序了
class Solution:
data = []
def Insert(self, num):
self.data.append(num)
self.data.sort()
return self.data
def GetMedian(self,n):
l = len(self.data)
if l%2==0:
return (self.data[l/2]+self.data[l/2 - 1])/2.0
else:
return self.data[l/2]
64.滑动窗口的最大值
# -*- coding:utf-8 -*-
class Solution:
def maxInWindows(self, num, size):
# write code here
if not num or not size:
return []
res = []
start = 0
end = size
while end <= len(num):
res.append(max(num[start:end]))
start+=1
end+=1
return res
65. 矩阵中的路径
用递归思路求解，判断当前字符的上下左右中是否有路径中的下一个字符
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
for i in range(rows):
for j in range(cols):
if matrix[i*cols+j] == path[0]:
if self.find(list(matrix),rows,cols,path[1:],i,j):
return True
return False
def find(self,matrix,rows,cols,path,i,j):
if not path:
return True
matrix[i*cols+j]='0'
if j+1<cols and matrix[i*cols+j+1]==path[0]:
return self.find(matrix,rows,cols,path[1:],i,j+1)
elif j-1>=0 and matrix[i*cols+j-1]==path[0]:
return self.find(matrix,rows,cols,path[1:],i,j-1)
elif i+1<rows and matrix[(i+1)*cols+j]==path[0]:
return self.find(matrix,rows,cols,path[1:],i+1,j)
elif i-1>=0 and matrix[(i-1)*cols+j]==path[0]:
return self.find(matrix,rows,cols,path[1:],i-1,j)
else:
return False
66. 机器人的运动范围
核心思路：
1.从（0,0）开始走，判断当前节点是否为标准节点。
1.当前节点标记为0
2.节点在矩阵范围内
- 每成功一步标记当前位置为1，然后从当前位置往四个方向走，回到第一步
# -*- coding:utf-8 -*-
class Solution:
def movingCount(self, threshold, rows, cols):
# write code here
board = [[0 for _ in range(cols)] for _ in range(rows)]
def block(r,c):
s = sum(map(int,str(r)+str(c)))
return s>threshold
class Context:
acc = 0
def traverse(r,c):
if not (0<=r<rows and 0<=c<cols):
return
if board[r][c]!=0:
return
if board[r][c]==-1 or block(r,c):
board[r][c]=-1
return
board[r][c] = 1
Context.acc+=1
traverse(r+1,c)
traverse(r-1,c)
traverse(r,c+1)
traverse(r,c-1)
traverse(0,0)
return Context.acc
