【算法题】剑指offer之二叉树--python实现
程序员文章站
2024-03-18 09:46:40
...
重建二叉树
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
if len(pre) == 0:
return None
if len(pre) == 1:
return TreeNode(pre[0])
root = TreeNode(pre[0])
# i = tin.index(pre[0])
#
# tin_lchild = tin[:i]
# len_lchild = len(tin_lchild)
# pre_lchild = pre[1:1+len_lchild]
#
# tin_rchild = tin[i+1:]
# len_rchild = len(tin_rchild)
# pre_rchild = pre[1+len_lchild:]
root.left = self.reConstructBinaryTree(pre[1:1+len(tin[:tin.index(pre[0])])], tin[:tin.index(pre[0])])
root.right = self.reConstructBinaryTree(pre[1+len(tin[:tin.index(pre[0])]):], tin[tin.index(pre[0])+1:])
return root
笔记
递归★★★★★
class soultion:
def nove(self,n,a,b,c):
print(n,a,b,c)
if n == 1:
print(a,'------------>',c)
else:
self.nove(n-1,a,c,b)
self.nove(1,a,b,c)
self.nove(n-1,b,a,c)
if __name__ == "__main__":
a = soultion()
b = a.nove(3, 'A', 'B', 'C')
print(b)
上述程序的执行结构图如下所示：
四个字母分别代表传入的（n,a,b,c）
传入顺序：由左到右，由上到下。
判断对称二叉树
# -*- 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
if pRoot is None:
return True
return self.check(pRoot.left,pRoot.right)
def check(self,l,r):
if l == None and r == None:
return True
elif (l != None and r == None) or (l == None and r != None) or (l.val != r.val):
return False
return self.check(l.left,r.right) and self.check(l.right,r.left)
二叉树的下一个节点
题目分析：
# -*- 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 pNode.right != None:
r = pNode.right
while r.left:
r = r.left
return r
#无右子树
else:
#如果是根节点（无父节点）
if pNode.next == None:
return None
#如果不是根节点（有父节点）
else:
#如果是父节点的左孩子
if pNode == pNode.next.left:
return pNode.next
#如果是父节点的右孩子
else:
while pNode.next.next.left != pNode.next:
pNode = pNode.next
#没有符合条件的即是尾节点
if pNode.next.next == None:
return None
return pNode.next.next
把二叉树打印成多行
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
#用两个列表分别保存当前行节点和下一行节点
current = [pRoot]
next_layer = []
result = []
if pRoot is None:
return result
while current:
for i in current:
if i.left:
next_layer.append(i.left)
if i.right:
next_layer.append(i.right)
#每一层输出一行，重点在于下面的append（[]）,[]就表示了每层一行
result.append([i.val for i in current])
current,next_layer = next_layer,[]
return result
按之字形顺序打印二叉树
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Print(self, pRoot):
# write code here
current = [pRoot]
next_layer = []
result = []
deep = 0
if pRoot is None:
return result
while current:
deep += 1
for i in current:
if i.left:
next_layer.append(i.left)
if i.right:
next_layer.append(i.right)
if deep % 2 != 0:
result.append([i.val for i in current])
else:
#下面这两句话的含义是一样的，都是逆序遍历current[]
#result.append([current[len(current)-i-1].val for i in range(len(current))])
result.append([i.val for i in current[::-1]])
current,next_layer = next_layer,[]
return result
序列化二叉树
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.count = -1
def Serialize(self, root):
# write code here
# 下面的两种判断方式相同
# if root is None:
if not root:
#必须添加分隔符，否则两位数转化为字符串时会出现错误
return "#,"
#如果当前节点是父节点，则会继续递归
#如果当前节点是叶节点，则会返回“.val , # , #"
return str(root.val)+ ',' + self.Serialize(root.left) + self.Serialize(root.right)
def Deserialize(self, s):
# write code here
self.count += 1
#只是第一次进入函数时对字符串进行分割
#split操作返回的是一个列表，如果每次都进行split操作会报错
#因为第一次往后s变成了列表，列表没有split操作
if self.count == 0:
s = s.split(',')
if self.count >= len(s):
return None
root = None
if s[self.count] != "#":
root = TreeNode(int(s[self.count]))
root.left = self.Deserialize(s)
root.right = self.Deserialize(s)
return root
split示例
二叉搜索树的第k个结点
二叉搜索树
二叉搜索树也叫二叉排序树，它可以是一棵空树。它具有一下特点
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
- 没有键值（key）相等的节点
- 二叉搜索树的中序遍历结果是排好序的
二叉搜索树如下所示：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回对应节点TreeNode
def __init__(self):
self.li = []
self.serch_flag = False
self.node = None
def KthNode(self, pRoot, k):
# write code here
if k <= 0 or not pRoot:
return None
self.li = self.Tinorder(pRoot)
if len(self.li) < k:
return None
self.node = self.Serch(pRoot, self.li[k - 1])
return self.node
#二叉搜索树的中序遍历结果是排序好的
def Tinorder(self, pRoot):
"""中序遍历"""
if not pRoot:
return
self.Tinorder(pRoot.left)
self.li.append(pRoot.val)
self.Tinorder(pRoot.right)
return self.li
def Serch(self, pRoot, num):
"""数值搜索"""
if not pRoot:
return
if pRoot.val == num:
self.node = pRoot
self.Serch(pRoot.left,num)
self.Serch(pRoot.right,num)
return self.node
本题扩展–任意二叉树的第K个节点
思路：
- 首先利用前序遍历将二叉树存入列表
- 再对列表进行快速排序
- 然后在寻找节点
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回对应节点TreeNode
def __init__(self):
self.li = []
#self.serch_flag = False
self.node = None
def KthNode(self, pRoot, k):
# write code here
if k <= 0 or not pRoot:
return None
self.li = self.Perorder(pRoot)
if len(self.li) < k:
return None
self.li = self.Quick_sort(self.li, 0, len(self.li) - 1)
self.node = self.Serch(pRoot, self.li[k - 1])
return self.node
def Perorder(self, pRoot):
"""先序遍历"""
if not pRoot:
return
self.li.append(pRoot.val)
self.Perorder(pRoot.left)
self.Perorder(pRoot.right)
return self.li
def Quick_sort(self, alist, first, last):
"""快速排序"""
# 终止条件
if first >= last:
return alist
mid_value = alist[first]
low = first
high = last
while low < high:
while low < high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
while low < high and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
alist[low] = mid_value
self.Quick_sort(alist, first, low - 1)
self.Quick_sort(alist, low + 1, last)
return alist
def Serch(self, pRoot, num):
"""数值搜索"""
if not pRoot:
return
if pRoot.val == num:
#self.serch_flag = True
self.node = pRoot
self.Serch(pRoot.left,num)
self.Serch(pRoot.right,num)
return self.node
数据流中的中位数
方法一–锥排序
思路：
- 建立一个大顶锥，一个小顶锥，小顶锥用来存大的半数数据，大顶锥用来存小半数数据（小顶堆中的元素都大于等于大顶堆中的元素）
- 当数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中
- 当数目为奇数的时候，将这个值插入小顶堆中，再将小顶堆中根节点（即最小值）插入到大顶堆中
- 取中位数的时候，如果当前个数为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当前个数为奇数，显然是取小顶堆的根节点
# -*- coding:utf-8 -*-
#导入优先队列算法
from heapq import *
#在heapq中只有小顶锥，大顶锥则用取反实现
class Solution:
def __init__(self):
#创建一个堆，可以使用list来初始化为 []
self.heaps = [], []
self.count = 0
def Insert(self, num):
# write code here
small, large = self.heaps
if self.count % 2 == 0:
#heapq.heappush(heap, item)
#将 item 的值加入 heap 中，保持堆的不变性。
#heapq.heappushpop(heap, item)
#将 item 放入堆中，然后弹出并返回 heap 的最小元素。
"""
如果是偶数：
先将取反放入大顶锥
再将大顶锥的追锥顶pop出，并取反放入小顶锥
（由于大顶锥用来存小半数数据，且大顶锥是小顶锥取反实现，
因此大顶锥里面的数全为原始数据的相反数）
"""
#-num的负号表示大顶锥里面的数全为原始数据的相反数
#-heappushpop的负号表示小顶锥里面的数全为原始数据（即相反数的相反数）
heappush(small, -heappushpop(large, -num))
else:
"""
如果是奇数：
先将放入小顶锥
再将大顶锥的追锥顶pop出，并取反放入大顶锥
"""
heappush(large, -heappushpop(small, num))
self.count+=1
def GetMedian(self,ss):
# write code here
small,large = self.heaps
if self.count % 2 != 0:
return float(small[0])
return (small[0] - large[0]) / 2.0
方法二
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
#用来记录数据流的个数
self.count = 0
self.li = []
def Insert(self, num):
# write code here
self.li.append(num)
self.li.sort()
self.count+=1
#题目有问题，缺少一个参数。需要自己加上
def GetMedian(self,AA):
# write code here
if self.count % 2 == 0:
#牛客网python版本为2+，被除数需要写成小数形式
#python2 5/2 = 2
#python3 5/2 = 2.5
return (self.li[self.count//2-1]+self.li[self.count//2])/2.0
else:
return self.li[self.count//2]