二叉树插入
class TreeNode:
def __init__(self, val, left, right):
self.val = val
self.left = left
self.right = right
class BinarySearchTree:
def insert(self, root, val):
if root == None:
root = TreeNode(val, None, None)
else:
if val < root.val:
root.left = self.insert(root.left, val)
if val > root.val:
root.right = self.insert(root.right, val)
return root
def preOrder(self, root):
if root:
print root.val
self.preOrder(root.left)
self.preOrder(root.right)
Tree = BinarySearchTree()
root = None
for i in [1,2,3]:
root = Tree.insert(root, i)
Tree.preOrder(root)
有序数组创建二叉树
class Solution:
def sortedArrayToBST(self, num):
if not num:
return None
mid = len(num)//2 #“//”表示整数除法;“/”浮点数除法;
root = TreeNode(num[mid])
left = num[:mid]
right = num[mid+1:]
root.left = self.sortedArrayToBST(left)
root.right = self.sortedArrayToBST(right)
return root
遍历二叉树
algorithms/
前序 根左右
中序 左根右
后序 左右根
递归方式
class Tree(object):
def __init__(self,data,left,right):
self.data=data
self.left=left
self.right=right
def post_visit(Tree):
if Tree:
post_visit(Tree.left)
post_visit(Tree.right)
print Tree.data
def pre_visit(Tree):
if Tree:
print Tree.data
pre_visit(Tree.left)
pre_visit(Tree.right)
def in_visit(Tree):
if Tree:
in_visit(Tree.left)
print Tree.data
in_visit(Tree.right)
非递归
class TreeNode:
def __init__(self,value=None,leftNode=None,rightNode=None):
self.value = value
self.leftNode = leftNode
self.rightNode = rightNode
class Tree:
def __init__(self,root=None):
self.root = root
def preOrder(self):
if not self.root:
return
stackNode = []
stackNode.append(self.root)
while stackNode:
node = stackNode.pop()
print node.value,
if node.rightNode:
stackNode.append(node.rightNode)
if node.leftNode:
stackNode.append(node.leftNode)
平衡二叉树
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
class Solution:
def getDepth(self , Root):
if Root == None:
return 0;
lDepth = self.getDepth(Root.left);
rDepth = self.getDepth(Root.right);
return max(lDepth , rDepth) + 1;
def IsBalanced_Solution(self, pRoot):
if not pRoot:
return True
lDepth = self.getDepth(pRoot.left);
rDepth = self.getDepth(pRoot.right);
diff = lDepth - rDepth;
if diff < -1 or diff > 1:
return False;
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right);
判断一棵树是否为另一棵的子树
给定两棵二叉树,判断T2是否是T1某棵子数的结构。
T1序列化成字符串str1;
T2序列化成字符串str2;
用KMP算法判断str1中是否包含str2:如果str1包含str2,说明T1包含于T2结构一致的子树。
KMP算法
#KMP
def kmp_match(s, p):
m = len(s); n = len(p)
cur = 0#起始指针cur
table = partial_table(p)
while cur<=m-n:
for i in range(n):
if s[i+cur]!=p[i]:
cur += max(i - table[i-1], 1)#有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位
break
else:
return True
return False
#部分匹配表
def partial_table(p):
'''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''
prefix = set()
postfix = set()
ret = [0]
for i in range(1,len(p)):
prefix.add(p[:i])
postfix = {p[j:i+1] for j in range(1,i+1)}
ret.append(len((prefix&postfix or {''}).pop()))
return ret
网友评论