笔试题
链表数据结构的定义 链表的增加 删除节点 找链表的中间节点
class Node:
def __init__(self,data):
self.data=data
self.next=None
class Link:
#在链表中增加节点 创建链表
def __init__(self,item):
self.len=len(item)
if self.len<=0:
return
self.head=Node(item[0])
self.tail=self.head
j=1
while(j<self.len):
self.tail.next=Node(item[j])
self.tail=self.tail.next
j+=1
#根据值删除节点
def remove_node(self, value):
"""
删除值
:param value:
:return:
"""
cur = self.head
if cur is None:
return
pre=Node(0)
pre.next=cur
while cur:
if cur.data == value:
#这边开始
pre.next=cur.next
break
else:
pre=pre.next
cur=cur.next
def printlink(self):
"""
正序打印该链表
"""
if self.head == None:
print("该链表为空链表！")
p = self.head
while p != None:
print(p.data, end=" ")
p = p.next
a = Link([1, 2, 3, 4])
a.printlink()
print('\n')
a.remova_node(2) # 插入操作
a.printlink()
print('\n')
通过new node来创建头节点，在删除链表节点的过程中需要pre指针指向前面一个节点。
二叉树的定义、递归遍历以及非递归遍历
1.二叉树的定义
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
2.二叉树的遍历——递归
(1)前序遍历:根节点、左子树、右子树
(2)中序遍历:左子树、根节点、右子树
(3)后序遍历:左子树、右子树、根节点
class Solution(object):
#前序遍历：
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res=[]
def search(root,res):
if root==None:
return
res.append(root.val)
search(root.left,res)
search(root.right,res)
search(root,res)
return res
#中序遍历：
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res=[]
def search(root,res):
if root==None:
return
search(root.left,res)
res.append(root.val)
search(root.right,res)
search(root,res)
return res
#后序遍历：
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res=[]
def search(root,res):
if root==None:
return
search(root.left,res)
search(root.right,res)
res.append(root.val)
search(root,res)
return res
二叉树的遍历——非递归
（1）前序遍历
由于前序遍历是根节点、左子树、右子树，根据栈的性质所有先让右节点入栈，再让左节点入栈
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root==None:
return []
else:
res=[]
stack=[root]
while stack:
top=stack.pop()
if top:
res.append(top.val)
if top.right:
stack.append(top.right)
if top.left:
stack.append(top.left)
return res
（2）中序遍历
通过一个栈stack来保存遍历二叉树的中间节点，通过temp改变遍历的指针指向。
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
#非递归
if not root:
return []
temp = root
stack = []
res = []
while temp or stack:
while temp:
stack.append(temp)
temp = temp.left
if stack:
temp = stack.pop()
res.append(temp.val)
temp = temp.right
return res
（3）后序遍历
将前序遍历的过程反转一下，得到的结果是根节点、右子树、左子树，得到的结果再reverse即为后序遍历的结果。
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
#非递归
if root==None:
return []
else:
res=[]
stack=[root]
while stack:
top=stack.pop()
if top:
res.append(top.val)
if top.left:
stack.append(top.left)
if top.right:
stack.append(top.right)
return res[::-1]
